place or move solid on grids (heighmap)

hallo guys

i have a highmap grid used to create a terrain
now i would like to move same solid over it, i mean following the irregularities of the terrain
before to start the implementation i would like to see what are the possible implementations

my understanding is that the relation in terms of size between the solid (the car) and the size of the tile in the grid is very important
to have a more realistic effect is better that the tiles of the grid are more little that the size of the solid

to get the height of the map in a point i can add to terrain object a function
int height = terrain.getHeigth(Vector point)
this function try to find the height of the closest vertex on the grid

my idea was to get the point of the 4 wheel of the car, identify the height of each single point
and find a way to calulate the 2 angles rotation by z and x (if the grid is on x z plan)

now this is the real question!, the algorithm to calculate the rotation agles

still I don’t know what is the algotihym that i have to apply to generate the two angles
my idea was to computate angles in this way:
angel rotation by z) angle between the front wheels and angle back wheels and get the max or the average
angel rotation by x) angle between the left wheels and angle right wheels and get the max or the average

i can also verify if the angle is not over a limit and accept the movement, to avoid to have car that are able to go over the walls

i see different problem in this implementation, I mean in the result
immagine that i’m calculating the z angle and the terrain for the point of view of the front wheel as a slope in the opposit direction of the back wheel
same problme appear calculating the x angle if the slope of the right side is opposit of the left side

so i suppose that i’m using a worng alghoritm to computate the two rotation angles or may be i can not calculate the correct position with only 4 point but i nedd a 5th point that is the center of the solid

i dont know if i understand what you are trying to achieve …

  • sampling the grid with interpolation ?
  • extracting slope pitch and yaw angles ?
  • extracting the general slope-ness to threshold wallride ?

your plane is XZ (would be easier to read the following if i’d be XY).

sampling the point could be something like (pseudocode) …

float interpolatedHeightAtPoint( vec2 point_to_sample )
{
  vec2 sample         = point_to_sample / cellsize
  vec2 integerpart    = floor(sample);       // integer
  vec2 fractionalpart = fract(sample);       // float 0..1

  float a = get_height_at_cell( integerpart.x  , integerpart.y   ); // 4 vertices in the height-map
  float b = get_height_at_cell( integerpart.x+1, integerpart.y   );
  float c = get_height_at_cell( integerpart.x  , integerpart.y+1 );
  float d = get_height_at_cell( integerpart.x+1, integerpart.y+1 );

  return mix( mix( a, b, fractionalpart.x), mix( c, d, fractionalpart.x), fractionalpart.y);
}

basicly something like value/latice-noise.

extracting the angle could become a bit nasty. you could just grab the 4 edges of the cell you’re sampling the point in, and use pythagoras to get the angles … but only if your cell is a quad. usualy you end up with two triangles.

to get the slope-ness we could “dot” the normal at sampling point with “up”. we can do it analytical (fast) or with the central difference (easy) or maybe with a normal.

central difference would be something like (pseudo code) … the bigger eps is the smoother the normal should become … :

vec2 point;       // some point in worldspace 
float eps = 0.01; // magic number, should it match the cellsize ?

vec3 normal = vec3( interpolatedHeightAtPoint( vec2(point.x - eps, point.y)       ) - interpolatedHeightAtPoint( vec2(point.x + eps, point.y      ) ),
                    interpolatedHeightAtPoint( vec2(point.x,       point.y - eps) ) - interpolatedHeightAtPoint( vec2(point.x,       point.y + eps) ), 2.0 * eps );

     normal = normalize(normal);

we could caluculate the normal the same way we would calculate any triangle-normal (pseudocode) … should create a flat normal too … :

// assuming we have the four corner vertices of the cell we sample in ..

vec3 vertex_a;
vec3 vertex_b;
vec3 vertex_c;
vec3 vertex_d;

// assuming A B C are forming one triangle of the two possible.
// maybe we need to swizzle around and calc C B A if winding is CW.
// i dont know what to do with the 2nd triangle in the quad. maybe calculate it too and sum both ?
vec3 normal = cross(vertex_a.x - vertex_b.x, vertex_a.y - vertex_b.y, vertex_a.z - vertex_b.z, vertex_a.x - vertex_c.x, vertex_a.y - vertex_c.y, vertex_a.z - vertex_c.z);
     normal = normalize(normal);


we could calculate the normal analytical (pseudocode) … should create a flat normal too …


float deriv(vec2 value)
{
  return 1.0 - abs(value * 2.0 - 1.0); // a triangle. 
  //    return abs(value * 2.0 - 1.0); // or is this correct ?
}

float interpolatedHeightAndNormalAtPoint( vec2 point_to_sample, out vec3 normal_output )
{
  // just like the other method ..
  vec2 sample         = point_to_sample / cellsize
  vec2 integerpart    = floor(sample);       // integer
  vec2 fractionalpart = fract(sample);       // float 0..1

  float a = get_height_at_cell( integerpart.x  , integerpart.y   ); // 4 vertices in the height-map
  float b = get_height_at_cell( integerpart.x+1, integerpart.y   );
  float c = get_height_at_cell( integerpart.x  , integerpart.y+1 );
  float d = get_height_at_cell( integerpart.x+1, integerpart.y+1 );

  // and the normal ..

  vec2 dv = deriv(fractionalpart);

  normal.x = dv.x * mix( b-a, d-c, fractionalpart.y);
  normal.y = dv.y * mix( c-a, d-b, fractionalpart.x);
  normal.z = 1.0;  // not sure about this (z pointing up)

  normal = normalize(normal); // maybe not required

  return mix( mix( a, b, fractionalpart.x), mix( c, d, fractionalpart.x), fractionalpart.y);
}

now with the normal you can do something like …

float slope = dot(normal, vec3( 0.0, 0.0, 1.0 )); // Z pointing up, not Y in this example.

if( slope ==  1.0 ) { /* driving on super flat surface */ }
if( slope ==  0.0 ) { /* driving on a perfectly aligned wall */ }
if( slope == -1.0 ) { /* driving on the ceiling */ }

//

i have no idea if that code is correct, i did not test it. it’s just glsl-like-pseudocode. :slight_smile:

hallo basil_

thanks for your help, but unfortunally it is not my problem :frowning:
sorry if my english is not enough good and I have let you lost time try to find an alghortim :slight_smile:

i know how to calculate the height of the grid in one point
moreover in the my grid structure I mantain also the normal of each vertex so i can obtain easily it and computate the slope pitch and yaw

my problem is another, i will try to explane at the better that i can

my grid is based on triangles
i would like to place vehicles like a car and move it on the grid, the car is something that can be considered schematically as a box

a car has 4 wheels, I know exactly the coordinate of this 4 point (i can computate normal, heigth… etcc in this point becouse i have all the info)
and this are the 4 points that can enter in contact with the grid
so I would like to find a way to calculate the rotation that i have to apply to the center of gravity of the car

if we considered the grid based on the x,y axis
i need only to calculate the rotation by the x and y axis becouse they are the rotatio that place the wheels in contact with the grid

becouse the z is used only to positionate the car in the direction of the movement

so my problem is to find a good idea to calculate the x and y angles considering that i have 4 point,

i know also that 4 point of the wheels are not enought, immagine this scenario:
-that the car is moving on a little hill (a sort of spike)
-the 4 wheels are located in a point lower down that the the peak of the hill

so the result is that when i will render the car, the wheels are correctly on the grid but may be part of the terrain (the grid)
will be draw inside the car

so if someone can suggest a better algorhitm,

for example another idea could be to conside the 5 points, adding the center of gravity of the car traslated at the level of the wheels as another point that has to be evaluated to computate the x and y angles rotations

or I can consider the 4 point of the wheel of the car, as two triangles (wheel ABC and wheel BCD), and use algorithms for intersections of the triangles to identify the intersections points, and based on the intersections point computate the x and y angles rotations

i never do something like this so i would like to know what is the best approach to achieve this kind of problems

ah no worries, i’m not native neither and i would not post if wouldn’t like to :wink:

i like your idea with the 5th point. doing everything with just a few points would be pretty fast. tho’ i cannot give a good hint how to calculate it. would just implement it naively and probably calculate it more then once each game-step to get better accuracy. i believe there is no 100% perfect solution to that tbh.

personally i would go into simulating the physics, with 4 springs connecting the wheels with the chassis, and intersecting the chassis with the terrain itself. way more calculation to do tho’, probably much slower - but probably more fun to play later on :wink:

i think that way cos’ i picture the scenario we would end up following the correct and fast calculation. it may be not too good if you think about adding more ideas to it. something like collision with other vehicles or static objects or interacting with particles. we might end up with a huge list of things we need to consider each game-step. maintaining something like that could become annoying.

that’s just my personal preference. i would go into a more generic direction and think about vehicle-simulation and ensure extending it later would not get me stuck. i would give jbullet a go with http://jbullet.advel.cz/ and code it from scratch at the same time, just to learn :slight_smile:

o/