3D with Allegro 5
Edgar Reynaldo

Hi all, I've been given an assignment to find the shortest path on a graph of 3D vertices using Djikstra's algorithm or similar. That's not the part I want help with - I want to draw a 3D model of the graph with lines on the edges and dots on the vertices. I have the graph info in a file and I will read it in and have the vertex data available to pass to Allegro. Question - what do I use and where do I start? I'm totally new to 3D graphics and don't know yet the basics of how to get a 3D image on screen with Allegro 5. I can use al_draw_prim with ALLEGRO_PRIM_POINT_LIST and ALLEGRO_PRIM_LINE_LIST but how do I set up the 3D perspective to draw it with?

Let's assume the world is centered on 0.0,0.0,0.0 and we're looking at it from a given distance away in any direction. We have an angle on the xy plane and an angle on the yz plane. How do I turn those into the proper perspective and use it with Allegro 5. How do I turn that into something I can use with al_perspective_transform? And what are left,top,n(ear),right,bottom, and f(ar)? After I figure out that part it's just a matter of translation and rotation I would think, right?

SiegeLord

Elias recently added an ex_camera example (adapted from Allegro 4) that you could look at. There's a reasonable discussion about the perspective transform parameters here.

Edgar Reynaldo

Okay, I'm starting to understand what stuff means, but how do I get the values for r,l,t,b,n, and f from a 3D angle? Do I have to calculate the pyramidal frustum myself?

Finally, we found all entries of GL_PROJECTION matrix. The complete projection matrix is;

{"name":"gl_projectionmatrix01.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/1\/81ee78b0ef2b14c60ec8ba79bf2fff86.png","w":470,"h":230,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/1\/81ee78b0ef2b14c60ec8ba79bf2fff86"}

SiegeLord

Those have nothing to do with the orientation where you are looking at. Your actual code would look something like this:

ALLEGRO_TRANSFORM t;

al_identity_transform(&t);
al_perspective_transform(&t, ...);
al_use_projection_transform(&t);

al_build_camera_transform(&t, /* this is where your angles will come in */);
al_use_transform(&t);


Edgar Reynaldo
SiegeLord said:

Those have nothing to do with the orientation where you are looking at. Your actual code would look something like this:

Oh! Okay! So what do near and far have to do with it then? Dont' they sort of determine the distance from the camera to the clipping planes?

And why are there two transformations in use now? I dont' get the differnce between al_use_projection_transform and al_use_transform.

In your code example you don't call al_identity_transform on the transform before calling al_build_camera_transform and after using al_use_projection_transform. Is that on purpose?

Edit
l,r,t, and b are all determined by the horizontal and vertical field of view, correct? Ie - the interior angles of the frustum, right?

Elias

And why are there two transformations in use now?

They are applied one after the other. But the projection transform depends on the screen size so there's good reasons to keep them separate.

Quote:

In your code example you don't call al_identity_transform on the transform before calling al_build_camera_transform and after using al_use_projection_transform. Is that on purpose?

al_perspective_transform modifies the transform you pass, al_build_camera_transform overwrites it, so in one case you need to initialize first in the other not.

Quote:

l,r,t, and b are all determined by the horizontal and vertical field of view, correct? Ie - the interior angles of the frustum, right?

Yes. Or rather, the quotient of the near plane to those four decides the horizontal/vertical field of view. So you can first choose your clipping distance and then set those four according to your fov. (Or the other way around, both ways work.)

Edgar Reynaldo

Do I need to position my camera farther away because of the near clipping plane? What if the z value of near was like 10 or 100? Do I need to move my camera back by that same amount to bring objects on the near clipping plane into view?

Elias

Yes, anything behind (closer to the camera than) the near clipping plane will not be visible.

Edgar Reynaldo

Okay, so I don't get yet how the perspective transform is supposed to be composed. Am I supposed to set l,r,t,b,n,and f as if I was looking directly down the negative z axis in the left hand side of the graphic I posted above? Ie - what would happen if l and r and t and b aren't symettric? What if they don't equal their negated counterpart? Does that skew the perspective or what does it do? I suppose I should just play around with it a bit but I like to ask questions.

Also, I was discussing on IRC earlier about whether I should render 3D points and lines as 3D spheres or cubes and rectangular prisms or right cylinders. Is there a good way to go about triangulating those 3D shapes if it turns out that the points and lines dont' look right with al_draw_prim? I mean, how does allegro decide how thick to draw a 2D line in 3D space? Or a 1D point in 3D space?

Mark Oates

Hey Edgar, post screenshots of your progres? I'm interested to see how it all comes together for you

Edgar Reynaldo

Oh, definitely. I should have a prototype ready relatively soon.

I have to do some reading on the Spherical Coordinate System and the Cylindrical Coordinate System first though. There's a nice set of conversion functions on each page.

Edit - need to get a pesky up vector for the camera transform!

Most commercial games use the cross product to generate a perpendicular.

Take the cross product of your look vector and a vector of 0,1,0. This gives you your right vector.

Take the cross product of your right vector and your look vector. This is your new up vector, which is a perpendicular to your original look vector.

Edit2
Just gonna use 0,1,0 for the up vector for now until I have a proper vector class.

Here are the initial results (expand to see the actual images, the graph I'm supposed to find the shortest path with is on the right ) :
Blue is a from edge blending to green is a to edge with red dots for the actual vertices. It looks like there is some kind of method to the madness on the right!
{"name":"609382","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/6\/c6ccea15f1e464abc5b21c75b3bfdd7b.png","w":606,"h":625,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/6\/c6ccea15f1e464abc5b21c75b3bfdd7b"} {"name":"609384","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1db2c8241cc52ed110803896c275d303.png","w":606,"h":625,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1db2c8241cc52ed110803896c275d303"}

Produced with :

This is a total hack for now, as I only check for key presses and I'm not rotating around the universe center like I want to just yet. But you can move 1 unit in all the cardinal directions.

I'll share the full code once I have it more polished.

Question :
Is there a way for me to ignore the z-buffer for a certain set of edges? I want to show the shortest path without it being hidden by the vertices in front of it.

Elias

Is there a way for me to ignore the z-buffer for a certain set of edges?

If you can draw them with a separate al_draw_prim, then yes, do this before:
al_set_render_state(ALLEGRO_DEPTH_TEST, false);

Edgar Reynaldo

Edit - figured out how to reset the transform. See ResetView() below.

Ok, thanks. I can't seem to restore the default drawing transforms so I can draw text with al_draw_textf. Not sure how to do so.

Here's what I'm using :

If I uncomment the al_hold_bitmap_drawing calls things don't work right and it doesn't respect the camera, whether I have SetupView() before or imbetween them.

I made a small demo so you guys can try it out. Here it is (its a win32 binary, sorry no source yet) :
example1.7z

Keys are up down left right a and z. Esc quits the graphical part. help and quit will give you the rest of the commands.

The program processes vertexes and edges in format like this :
VERTEX2 0 0.0 0.0 0.0
VERTEX2 1 1.0 0.0 0.0
VERTEX2 2 0.0 1.0 0.0
EDGE2 0 1
EDGE2 1 2
EDGE2 0 2

The first number is simply the vertex id, it should just count up from 0. The next 3 numbers are the xyz coordinates of the vertex. The two numbers following the EDGE2 declaration are the vertex id's that the edge links to.

Mark Oates

Cool graphics

I have screenshots from the period when I crawled and scraped my way into 3D. I might dig them up later, they're quite art. Learning 3D is a bit like being placed in a strange universe and trying to grab onto something, so you can reliably anchor yourself, to then try grabbing onto something else. Eventually things start to fall into place and things get sorted out.

It was only a few months ago that I realized my entire 3D backend was completely flipped. The only anomaly I was able to witness was that textures were reversed, and I didn't really even notice that much until later, everything else seemed to work as expected. I think that's why several people reported strangely rendered polygons in A Slug's Life.

Edgar Reynaldo

Did you try the demo? https://www.allegro.cc/files/attachment/609385

It starts out with a double 4 sided pyramid and then shows that monster graph for the assignment with like 64000 edges. It slows down my laptop's fps a little bit when zooming in close but my desktop handled it no prob.

Features planned next :
1) Implement azimuth / zenith orientation. Azimuth is angle on the xy plane and zenith is declination from the positive z-axis. This requires a decent vector class.

2) Implement FACE2 faces. They should be fairly simple. Just store 3 VERTEX_ID's instead of 2 like an edge.
FACE2 0 1 2

3) Implement roll and yaw and pitch. This takes some more difficult trigonometry, but can all be implemented with al_rotate_transform_3d.

Edit

It now shows the current shortest path and a bounding prism of the universe data.
{"name":"609391","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/6\/e6346f3a5b635d1b40176235582531f5.png","w":606,"h":625,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/6\/e6346f3a5b635d1b40176235582531f5"}

Do you guys realize what you can use Djikstra's algorithm for? Not only could you solve mazes with relative ease by finding the shortest path but you could also use it for A* pathfinding in a game where you need your AI to respond to obstacles smoothly. Just don't put any vertices on the points where there are obstacles, and it will avoid them automatically finding the shortest path around. If you need your NPC's to attack monsters in range give the closer the monster the higher the attraction value, and then find the maximum path, where it fulfills the most objectives and maximizes value.

beoran

Since my main game project is going sluggishly I decide to make it go even more slowly by trying to make a basic "3D" dungeon crawler with Allegro, so examples like these are very useful.

And yes, Dijkstra's algorithm is cool when properly parametrized.

Edgar Reynaldo

Can anyone explain the source of corruption in my vertice drawing? The white lines are supposed to be the edges of a bounding prism surrounding the universe, but sometimes they don't get drawn right, and they do this :
{"name":"609392","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c21550024b21a4efa32829fe62f4cf.png","w":612,"h":632,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c21550024b21a4efa32829fe62f4cf"}

Here's the code I use to draw everything :

1 2void Visualizer::Draw() { 3 4///int al_draw_prim(const void* vtxs, const ALLEGRO_VERTEX_DECL* decl, ALLEGRO_BITMAP* texture, int start, int end, int type) 5 6 const ALLEGRO_VERTEX bounding_vertices[8] = { 7 {gxmin , gymin, gzmin, 0.0 , 0.0 , al_map_rgb(255,255,255)},// lbn 8 {gxmin , gymin, gzmax, 0.0 , 0.0 , al_map_rgb(255,255,255)},// lbf 9 {gxmin , gymax, gzmax, 0.0 , 0.0 , al_map_rgb(255,255,255)},// ltf 10 {gxmin , gymax, gzmin, 0.0 , 0.0 , al_map_rgb(255,255,255)},// ltn 11 {gxmax , gymin, gzmin, 0.0 , 0.0 , al_map_rgb(255,255,255)},// rbn 12 {gxmax , gymin, gzmax, 0.0 , 0.0 , al_map_rgb(255,255,255)},// rbf 13 {gxmax , gymax, gzmax, 0.0 , 0.0 , al_map_rgb(255,255,255)},// rtf 14 {gxmax , gymax, gzmin, 0.0 , 0.0 , al_map_rgb(255,255,255)} // rtn 15 }; 16//*/ 17 const ALLEGRO_VERTEX bounding_edge_vertices[12*2] = { 18 bounding_vertices[0] , bounding_vertices[1] , 19 bounding_vertices[1] , bounding_vertices[2] , 20 bounding_vertices[2] , bounding_vertices[3] , 21 bounding_vertices[3] , bounding_vertices[0] , 22 bounding_vertices[4] , bounding_vertices[5] , 23 bounding_vertices[5] , bounding_vertices[6] , 24 bounding_vertices[6] , bounding_vertices[7] , 25 bounding_vertices[7] , bounding_vertices[4] , 26 bounding_vertices[0] , bounding_vertices[4] , 27 bounding_vertices[1] , bounding_vertices[5] , 28 bounding_vertices[2] , bounding_vertices[6] , 29 bounding_vertices[3] , bounding_vertices[7] 30 }; 31 32// al_hold_bitmap_drawing(true); 33 34 SetupView(); 35 36 al_set_render_state(ALLEGRO_DEPTH_TEST, true); 37 38 // draw edges vertices and then the vertices 39 if (allegro_edges) { 40 al_draw_prim(allegro_edges , 0 , 0 , 0 , nallegro_edges , ALLEGRO_PRIM_LINE_LIST); 41 } 42 if (allegro_vertices) { 43 al_draw_prim(allegro_vertices , 0 , 0 , 0 , nallegro_vertices , ALLEGRO_PRIM_POINT_LIST); 44 } 45 if (draw_bounds) { 46// if (bounding_edge_vertices) { 47 al_draw_prim(bounding_edge_vertices , 0 , 0 , 0 , 24 , ALLEGRO_PRIM_LINE_LIST); 48// } 49 } 50 al_set_render_state(ALLEGRO_DEPTH_TEST, false); 51 52 if (allegro_shortest_path) { 53// printf("nallegro_shortest_path = %u\n" , nallegro_shortest_path); 54 al_draw_prim(allegro_shortest_path , 0 , 0 , 0 , nallegro_shortest_path , ALLEGRO_PRIM_LINE_STRIP); 55 } 56 57 /// TODO Draw shortest path 58 59// al_hold_bitmap_drawing(false); 60 ResetView(); 61 62 al_draw_textf(font , al_map_rgb(255,255,255) , 10.0 , 10.0 , 0 , 63 "xyz = (%lf,%lf,%lf)" , transx , transy , transz); 64 65 al_draw_textf(font , al_map_rgb(255,255,255) , 10.0 , 570.0 , 0 , 66 "gEsz = %u , nallegro_edges = %u, directed = %s" , graph.ESize() , nallegro_edges , graph.Directed()?"true":"false"); 67 68 69// printf("xyz = (%lf,%lf,%lf) urad = %lf\n" , transx , transy , transz , urad); 70 71}

I can't explain why last night the bounding prism was drawn correctly and now it is not. It works for smaller graphs though, which I don't get.