Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Fast way to calculate heightmap normals


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 RajanSky   Banned   -  Reputation: 100

Like
Likes
Like

Posted 18 June 2003 - 07:03 AM

Hi! My friend and I are working on optimizing a terrain system and a water rendering system which involve dynamic deformations every frame. Besides the fact that we''re constantly locking and unlocking our vertex buffers, one of our slowdowns is that we have to re-calculate the normals whenever the surface deforms, which is very expensive using the standard method. (Take the cross product of two vectors from a triangle) So, I remember in Yann''s water rendering lecture, he provided some code which calculates the normals directly from a heightmap based on height differentials. We tried this and it works (we got an instant 20% speedup), but we had to create some "fudge factor" to scale the Z component of the vector. Here''s the basic algorithm... At every vertex of the heightmap, you compute the components of your normal vector as: for y = 0 to ySize - 1 for x = 0 to xSize - 1 n.x = Height[x-1][y] - Height[x+1][y]; n.y = Height[x][y-1] - Height[x][y+1]; n.z = 2 / xSize + 2 / ySize; normalize(n); next x next y Where Height is a heightmap, and xSize and ySize are the dimensions of the heightMap... Anyways, I think this formula makes some assumptions about the ranges of values used for the heights and the spacing of the vertices in world coordinates. So, to get it to work for us, we had to multiply the z component by 100 (fudge factor). This is just a hack though, so does anyone know how this works, and in particular, how the Z-component is derived? If anyone has any insight on how this works or how to fix it I''d really appreciate it! Thank you very much, Raj

Sponsor:

#2 JohnBolton   Members   -  Reputation: 1372

Like
Likes
Like

Posted 20 June 2003 - 05:52 AM

It is not a hack. It is actually the result of taking out all the redundant cross-product calculations. Here is my code for comparison:



static Vector3f ComputeGridNormal( HeightField const & hf, int x, int y )
{
// The 4 adjacent points in a uniform grid: A, B, C, D

//

// B

// |

// C--0--A

// |

// D

//

//

// The ratio of XY-scale to Z-scale: s = Sxy / Sz

// The desired normal: N = cross(A,B) + cross(B,C) + cross(C,D) + cross(D,A), (then normalize)

//

// N.x = 2 * s * (C.z - A.z)

// N.y = 2 * s * (D.z - B.z)

// N.z = 4 * s^2

// normalize( N )

//

// Since N is normalized in the end, it can be divided by 2 * s:

//

// N.x = C.z - A.z

// N.y = D.z - B.z

// N.z = 2 * s

// normalize( N )

//


HeightField::Vertex const * const paV = hf.GetData( x, y );
int const sx = hf.GetSizeX();
int const sy = hf.GetSizeY();
float const scale = hf.GetXYScale();

float const z0 = paV[ 0 ].m_Z;

float const Az = ( x + 1 < sx ) ? ( paV[ 1 ].m_Z ) : z0;
float const Bz = ( y + 1 < sy ) ? ( paV[ sx ].m_Z ) : z0;
float const Cz = ( x - 1 >= 0 ) ? ( paV[ -1 ].m_Z ) : z0;
float const Dz = ( y - 1 >= 0 ) ? ( paV[ -sx ].m_Z ) : z0;

return Vector3( Cz - Az, Dz - Bz, 2.f * scale ).Normalize();
}


[edited by - Jambolo on June 20, 2003 1:05:45 PM]

#3 RajanSky   Banned   -  Reputation: 100

Like
Likes
Like

Posted 23 June 2003 - 06:22 AM

Cool, thank you very much Jambolo! Now I have some idea where the formula comes from so finding the z component shouldn''t be too hard

Raj

#4 Mastaba   Members   -  Reputation: 757

Like
Likes
Like

Posted 25 June 2003 - 12:50 PM

Anyone care to do the algebra to see if what Jambolo says is true? I can''t, I''ve got c.t.s..

#5 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 25 June 2003 - 01:47 PM

Maple''s take on it:

> restart;
> with(linalg):
> assume(Ax,real);
> assume(Ay,real);
> assume(Az,real);
> assume(Bx,real);
> assume(By,real);
> assume(Bz,real);
> assume(Cx,real);
> assume(Cy,real);
> assume(Cz,real);
> assume(Fx,real);
> assume(Fy,real);
> assume(Fz,real);
> A:=array(1..3,[Ax,Ay,Az]):
> B:=array(1..3,[Bx,By,Bz]):
> C:=array(1..3,[Cx,Cy,Cz]):
> F:=array(1..3,[Fx,Fy,Fz]):
> N1:=normalize(crossprod(A,B)):
> N2:=normalize(crossprod(B,C)):
> N3:=normalize(crossprod(C,F)):
> N4:=normalize(crossprod(F,A)):
> N0:=normalize(N1+N2+N3+N4);
>
Warning, new definition for norm
Warning, new definition for trace

[/ Ay~ Bz~ - Az~ By~ By~ Cz~ - Bz~ Cy~
N0 := [|--------------------- + --------------------
[| 2 2 2 1/2 2 2 2 1/2
[\(%11 + %4 + %7 ) (%6 + %3 + %9 )

Cy~ Fz~ - Cz~ Fy~ Fy~ Az~ - Fz~ Ay~ \ / 1/2 /
+ --------------------- + ---------------------| / %13 , |
2 2 2 1/2 2 2 2 1/2| / |
(%8 + %2 + %12 ) (%1 + %5 + %10 ) / \

Az~ Bx~ - Ax~ Bz~ Bz~ Cx~ - Bx~ Cz~
--------------------- + --------------------
2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 )

Cz~ Fx~ - Cx~ Fz~ Fz~ Ax~ - Fx~ Az~ \ / 1/2 /
+ --------------------- + ---------------------| / %13 , |
2 2 2 1/2 2 2 2 1/2| / |
(%8 + %2 + %12 ) (%1 + %5 + %10 ) / \

Ax~ By~ - Ay~ Bx~ Bx~ Cy~ - By~ Cx~
--------------------- + --------------------
2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 )

Cx~ Fy~ - Cy~ Fx~ Fx~ Ay~ - Fy~ Ax~ \ / 1/2
]
+ --------------------- + ---------------------| / %13 ]
2 2 2 1/2 2 2 2 1/2| / ]
(%8 + %2 + %12 ) (%1 + %5 + %10 ) / ]

%1 := | Fy~ Az~ - Fz~ Ay~ |

%2 := | Cz~ Fx~ - Cx~ Fz~ |

%3 := | Bz~ Cx~ - Bx~ Cz~ |

%4 := | Az~ Bx~ - Ax~ Bz~ |

%5 := | Fz~ Ax~ - Fx~ Az~ |

%6 := | By~ Cz~ - Bz~ Cy~ |

%7 := | Ax~ By~ - Ay~ Bx~ |

%8 := | Cy~ Fz~ - Cz~ Fy~ |

%9 := | Bx~ Cy~ - By~ Cx~ |

%10 := | Fx~ Ay~ - Fy~ Ax~ |

%11 := | Ay~ Bz~ - Az~ By~ |

%12 := | Cx~ Fy~ - Cy~ Fx~ |

2 2 2 1/2 2 2 2 1/2
%13 := (| (%6 + %3 + %9 ) (%8 + %2 + %12 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Ay~ Bz~ - (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 1/2
(%8 + %2 + %12 ) (%1 + %5 + %10 ) Az~ By~ +

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%8 + %2 + %12 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
By~ Cz~ - (%11 + %4 + %7 ) (%8 + %2 + %12 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Bz~ Cy~ + (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2
(%6 + %3 + %9 ) (%1 + %5 + %10 ) Cy~ Fz~ -

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
Cz~ Fy~ + (%11 + %4 + %7 ) (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 1/2
(%8 + %2 + %12 ) Fy~ Az~ - (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2 2
(%6 + %3 + %9 ) (%8 + %2 + %12 ) Fz~ Ay~ | + |

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%6 + %3 + %9 ) (%8 + %2 + %12 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
Az~ Bx~ - (%6 + %3 + %9 ) (%8 + %2 + %12 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Ax~ Bz~ + (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2
(%8 + %2 + %12 ) (%1 + %5 + %10 ) Bz~ Cx~ -

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%8 + %2 + %12 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
Bx~ Cz~ + (%11 + %4 + %7 ) (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Cz~ Fx~ - (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2
(%6 + %3 + %9 ) (%1 + %5 + %10 ) Cx~ Fz~ +

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 ) (%8 + %2 + %12 )

2 2 2 1/2 2 2 2 1/2
Fz~ Ax~ - (%11 + %4 + %7 ) (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 2 1/2
(%8 + %2 + %12 ) Fx~ Az~ | + | (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 1/2
(%8 + %2 + %12 ) (%1 + %5 + %10 ) Ax~ By~ -

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%6 + %3 + %9 ) (%8 + %2 + %12 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
Ay~ Bx~ + (%11 + %4 + %7 ) (%8 + %2 + %12 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Bx~ Cy~ - (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2
(%8 + %2 + %12 ) (%1 + %5 + %10 ) By~ Cx~ +

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 ) (%1 + %5 + %10 )

2 2 2 1/2 2 2 2 1/2
Cx~ Fy~ - (%11 + %4 + %7 ) (%6 + %3 + %9 )

2 2 2 1/2 2 2 2 1/2
(%1 + %5 + %10 ) Cy~ Fx~ + (%11 + %4 + %7 )

2 2 2 1/2 2 2 2 1/2
(%6 + %3 + %9 ) (%8 + %2 + %12 ) Fx~ Ay~ -

2 2 2 1/2 2 2 2 1/2 2 2 2 1/2
(%11 + %4 + %7 ) (%6 + %3 + %9 ) (%8 + %2 + %12 )

2 / 2 2 2 2 2 2 2 2
Fy~ Ax~ | ) / (%4 %3 %2 %5 + %4 %3 %2 %10
/

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %6 %2 %1 + %11 %6 %2 %5 + %11 %6 %2 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %6 %12 %1 + %11 %6 %12 %5 + %11 %6 %12 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %6 %2 %10 + %4 %9 %8 %1 + %4 %9 %8 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %9 %8 %10 + %4 %6 %8 %1 + %4 %6 %8 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %6 %8 %10 + %4 %6 %2 %1 + %4 %6 %2 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %6 %2 %10 + %4 %6 %12 %1 + %4 %6 %12 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %6 %12 %10 + %4 %3 %8 %1 + %4 %3 %8 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %3 %8 %10 + %7 %9 %8 %5 + %7 %9 %8 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %3 %12 %1 + %4 %3 %12 %5 + %4 %3 %12 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %9 %2 %1 + %4 %9 %2 %5 + %4 %9 %2 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %4 %9 %12 %1 + %4 %9 %12 %5 + %4 %9 %12 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %6 %8 %1 + %7 %6 %8 %5 + %7 %6 %8 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %6 %2 %1 + %7 %3 %8 %1 + %11 %3 %8 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %6 %12 %1 + %7 %6 %12 %5 + %7 %6 %12 %10

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %3 %8 %5 + %7 %3 %8 %10 + %7 %3 %2 %1

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %3 %2 %5 + %7 %3 %2 %10 + %7 %3 %12 %1

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %3 %12 %5 + %7 %3 %12 %10 + %11 %9 %12 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %9 %12 %10 + %11 %6 %8 %1 + %11 %6 %8 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %6 %8 %10 + %11 %3 %12 %1 + %11 %3 %12 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %9 %12 %1 + %11 %3 %12 %10 + %7 %9 %2 %1

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %9 %2 %5 + %7 %9 %2 %10 + %7 %9 %12 %1

2 2 2 2 2 2 2 2 2 2 2 2
+ %7 %9 %12 %5 + %7 %9 %12 %10 + %11 %3 %8 %1

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %3 %8 %5 + %11 %3 %2 %1 + %11 %3 %2 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %3 %2 %10 + %11 %9 %8 %1 + %11 %9 %8 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %9 %8 %10 + %11 %9 %2 %1 + %11 %9 %2 %5

2 2 2 2 2 2 2 2 2 2 2 2
+ %11 %9 %2 %10 + %7 %9 %8 %1 + %7 %6 %2 %5

2 2 2 2
+ %4 %3 %2 %1 )


No matter what I tried, I couldn''t get it to simplify any farther.

#6 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 25 June 2003 - 02:26 PM

I should add the reason I couldn''t get Maple to simplify it is that it kept saying the object was too large for the student edition to simplfy.

#7 JohnBolton   Members   -  Reputation: 1372

Like
Likes
Like

Posted 29 June 2003 - 12:41 PM

quote:
Original post by Mastaba
Anyone care to do the algebra to see if what Jambolo says is true? I can't, I've got c.t.s..
         B
|
C--0--A
|
D

N = AxB + BxC + CxD + DxA, then normalize

note: this is an axis-aligned uniform grid and the distance between the points in the XY plane is Sxy, so Ax = By = -Cx = -Dy = Sxy, and Ay = Bx = Cy = Dx = 0
note: Actual z values may be scaled and this factor must be included in the calculation (e.g. if 0-1000 is scaled to 0-255, Sz = .255)


Nx = Ay*Bz/Sz - Az/Sz*By + By*Cz/Sz - Bz/Sz*Cy + Cy*Dz/Sz - Cz/Sz*Dy + Dy*Az/Sz - Dz/Sz*Ay
= 0 - Sxy*Az/Sz + Sxy*Cz/Sz - 0 + 0 - -Sxy*Cz/Sz + -Sxy*Az/Sz - 0
= Sxy / Sz * ( -Az + Cz + Cz - Az )
= 2 * Sxy / Sz * ( Cz - Az )

Ny = Az/Sz*Bx - Ax*Bz/Sz + Bz/Sz*Cx - Bx*Cz/Sz + Cz/Sz*Dx - Cx*Dz/Sz + Dz/Sz*Ax - Dx*Az/Sz
= 0 - Sxy*Bz/Sz + -Sxy*Bz/Sz - 0 + 0 - -Sxy*Dz/Sz + Sxy*Dz/Sz - 0
= Sxy / Sz * ( -Bz - Bz + Dz + Dz )
= 2 * Sxy / Sz * ( Dz - Bz )

Nz = Ax*By - Ay*Bx + Bx*Cy - By*Cx + Cx*Dy - Cy*Dx + Dx*Ay - Dy*Ax
= Sxy*Sxy - 0 + 0 - -Sxy*Sxy + Sxy*Sxy - 0 + 0 - -Sxy*Sxy
= 4 * Sxy * Sxy

Scale N by 1/2 * Sz/Sxy:

Nx = Cz - Az
Ny = Dz - Bz
Nz = 2 * Sxy * Sz

Normalize.

Hmm! The z value is different! I'm going to have to find out if it affects my code.

Also, it may be inconvenient for Sz to be calculated as Sz = zscaled / zActual. If Sz = zActual / zscaled, then
Nz = 2 * Sxy / Sz



[edited by - JohnBolton on June 30, 2003 12:38:03 PM]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS