
3D with Allegro 5 
Edgar Reynaldo
Member #8,592
May 2007

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
Member #7,827
October 2006

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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Edgar Reynaldo
Member #8,592
May 2007

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
Member #7,827
October 2006

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);
"For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Edgar Reynaldo
Member #8,592
May 2007

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 
Elias
Member #358
May 2000

Edgar Reynaldo said: 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
Member #8,592
May 2007

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
Member #358
May 2000

Yes, anything behind (closer to the camera than) the near clipping plane will not be visible.  
Edgar Reynaldo
Member #8,592
May 2007

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
Member #1,146
March 2001

Hey Edgar, post screenshots of your progres? I'm interested to see how it all comes together for you 
Edgar Reynaldo
Member #8,592
May 2007

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! Stackoverflow said: Most commercial games use the cross product to generate a perpendicular. Normalize your look vector. 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 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 ) : Produced with : 1
2void Visualizer::CalculateGraphCenter() {
3 gcx = 0.0;
4 gcy = 0.0;
5 gcz = 0.0;
6
7 if (nallegro_vertices < 1) {return;}
8
9 double ax = 0.0;
10 double ay = 0.0;
11 double az = 0.0;
12 for (SIZE_T i = 0 ; i < nallegro_vertices ; ++i) {
13 ax += allegro_vertices[i].x;
14 ay += allegro_vertices[i].y;
15 az += allegro_vertices[i].z;
16 }
17
18 gcx = ax/nallegro_vertices;
19 gcy = ay/nallegro_vertices;
20 gcz = az/nallegro_vertices;
21
22}
23
24
25
26void Visualizer::CalculateUniverseRadius() {
27 urad = 0.0;
28 for (SIZE_T i = 0 ; i < graph.VSize() ; ++i) {
29 const Vertex* v = &graph.Vertices()[i];
30 double dx = v>vx  gcx;
31 double dy = v>vy  gcx;
32 double dz = v>vz  gcx;
33 double vrad = sqrt(dx*dx + dy*dy + dz*dz);
34 if (vrad > urad) {
35 urad = vrad;
36 }
37 }
38}
39
40
41
42void Visualizer::ResetCamera() {
43
44
45
46
47/// cos(azimuth_angle_phi);
48
49 cam_x = gcx + transx;
50 cam_y = gcy + transy + 2.5;
51/// cam_sled_z = 3.0*urad;
52 cam_sled_z = 2.0*urad;
53 cam_z = gcz + transz + cam_sled_z;
54 cam_zenith_theta = 0.0;
55 cam_azimuth_phi = M_PI/2.0;
56// cam_view_vector_x = 0.0;
57// cam_view_vector_y = 0.0;
58// cam_view_vector_z = 0.0;
59
60}
61
62
63
64void Visualizer::InputLoop() {
65
66
67
68 bool quit = false;
69 bool redraw = true;
70
71 while (!quit) {
72 do {
73 ALLEGRO_EVENT ev;
74 al_wait_for_event(queue , &ev);
75
76 if (ev.type == ALLEGRO_EVENT_DISPLAY_CLOSE) {
77 quit = true;
78 }
79 else if (ev.type == ALLEGRO_EVENT_KEY_DOWN) {
80 redraw = true;
81 int k = ev.keyboard.keycode;
82 if (k == ALLEGRO_KEY_ESCAPE) {
83 quit = true;
84 }
85 else if (k == ALLEGRO_KEY_LEFT) {
86 transx = 1.0;
87 }
88 else if (k == ALLEGRO_KEY_RIGHT) {
89 transx += 1.0;
90 }
91 else if (k == ALLEGRO_KEY_UP) {
92 transy += 1.0;
93 }
94 else if (k == ALLEGRO_KEY_DOWN) {
95 transy = 1.0;
96 }
97 else if (k == ALLEGRO_KEY_A) {
98 transz += 1.0;
99 }
100 else if (k == ALLEGRO_KEY_Z) {
101 transz = 1.0;
102 }
103 ResetCamera();
104 }
105
106 } while (!al_is_event_queue_empty(queue));
107
108 if (redraw) {
109 redraw = false;
110
111 al_clear_to_color(al_map_rgb(0,0,0));
112
113 Draw();
114
115 al_flip_display();
116 }
117 };
118
119}
120
121
122
123
124void Visualizer::SetupView() {
125 // set up projection
126 al_identity_transform(&proj_transform);
127 //ltnrbf
128/// al_perspective_transform(&proj_transform , urad/2.0 , urad/2.0 , urad , urad/2.0 , urad/2.0 , urad*3.0);
129 double rad = 1.0;
130 al_perspective_transform(&proj_transform , rad/2.0 , rad/2.0 , rad , rad/2.0 , rad/2.0 , urad*15.0);
131 al_use_projection_transform(&proj_transform);
132
133///void al_build_camera_transform(ALLEGRO_TRANSFORM *trans,
134/// float position_x, float position_y, float position_z,
135/// float look_x, float look_y, float look_z,
136/// float up_x, float up_y, float up_z)
137 al_build_camera_transform(&cam_transform , cam_x , cam_y , cam_z , gcx , gcy , gcz , 0.0 , 1.0 , 0.0);
138 al_use_transform(&cam_transform);
139
140
141}
142
143
144
145void Visualizer::Draw() {
146
147 SetupView();
148
149///int al_draw_prim(const void* vtxs, const ALLEGRO_VERTEX_DECL* decl, ALLEGRO_BITMAP* texture, int start, int end, int type)
150 // draw edges vertices and then the vertices
151 if (allegro_edges) {
152 printf("Drawing allegro edges\n");
153// al_draw_prim(allegro_edges , 0 , 0 , 0 , (nallegro_edges  1)*2/3 , ALLEGRO_PRIM_TRIANGLE_FAN);
154 al_draw_prim(allegro_edges , 0 , 0 , 0 , nallegro_edges , ALLEGRO_PRIM_LINE_LIST);
155 }
156 if (allegro_vertices) {
157 printf("Drawing allegro vertices\n");
158 al_draw_prim(allegro_vertices , 0 , 0 , 0 , nallegro_vertices , ALLEGRO_PRIM_POINT_LIST);
159// al_draw_prim(allegro_vertices , 0 , 0 , 0 , nallegro_vertices , ALLEGRO_PRIM_POINT_LIST);
160 }
161 /// Draw shortest path
162
163}
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 : 
Elias
Member #358
May 2000

Edgar Reynaldo said: Is there a way for me to ignore the zbuffer for a certain set of edges?
If you can draw them with a separate al_draw_prim, then yes, do this before:  
Edgar Reynaldo
Member #8,592
May 2007

Edit  figured out how to reset the transform. See ResetView() below. Ok, thanks. 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. 1
2void Visualizer::SetupView() {
3 // set up projection
4 al_identity_transform(&proj_transform);
5 //ltnrbf
6/// al_perspective_transform(&proj_transform , urad/2.0 , urad/2.0 , urad , urad/2.0 , urad/2.0 , urad*3.0);
7 double rad = 1.0;
8 al_perspective_transform(&proj_transform , rad/2.0 , rad/2.0 , rad , rad/2.0 , rad/2.0 , urad*15.0);
9 al_use_projection_transform(&proj_transform);
10
11///void al_build_camera_transform(ALLEGRO_TRANSFORM *trans,
12/// float position_x, float position_y, float position_z,
13/// float look_x, float look_y, float look_z,
14/// float up_x, float up_y, float up_z)
15 al_build_camera_transform(&cam_transform , cam_x , cam_y , cam_z , gcx , gcy , gcz , 0.0 , 1.0 , 0.0);
16 al_use_transform(&cam_transform);
17
18
19}
20
21
22
23void Visualizer::ResetView() {
24
25 ALLEGRO_TRANSFORM t;
26 al_identity_transform(&t);
27 al_use_transform(&t);
28
29 al_identity_transform(&proj_transform);
30 al_orthographic_transform(&proj_transform , 0 , 0 , 1 , 600 , 600 , 1);
31 al_use_projection_transform(&proj_transform);
32}
33
34
35void Visualizer::Draw() {
36
37///int al_draw_prim(const void* vtxs, const ALLEGRO_VERTEX_DECL* decl, ALLEGRO_BITMAP* texture, int start, int end, int type)
38// al_hold_bitmap_drawing(true);
39
40 SetupView();
41
42 // draw edges vertices and then the vertices
43 if (allegro_edges) {
44 al_draw_prim(allegro_edges , 0 , 0 , 0 , nallegro_edges , ALLEGRO_PRIM_LINE_LIST);
45 }
46 if (allegro_vertices) {
47 al_draw_prim(allegro_vertices , 0 , 0 , 0 , nallegro_vertices , ALLEGRO_PRIM_POINT_LIST);
48 }
49
50 if (allegro_shortest_path) {
51 al_draw_prim(allegro_shortest_path , 0 , 0 , 0 , nallegro_shortest_path , ALLEGRO_PRIM_LINE_STRIP);
52 }
53
54 /// TODO Draw shortest path
55
56// al_hold_bitmap_drawing(false);
57 ResetView();
58
59 al_draw_textf(font , al_map_rgb(255,255,255) , 10.0 , 10.0 , 0 ,
60 "xyz = (%lf,%lf,%lf)" , transx , transy , transz);
61
62 printf("xyz = (%lf,%lf,%lf) urad = %lf\n" , transx , transy , transz , urad);
63
64}
I made a small demo so you guys can try it out. Here it is (its a win32 binary, sorry no source yet) : 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 : 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
Member #1,146
March 2001

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
Member #8,592
May 2007

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 : 2) Implement FACE2 faces. They should be fairly simple. Just store 3 VERTEX_ID's instead of 2 like an edge. 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. 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
Member #12,636
March 2011

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
Member #8,592
May 2007

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 : 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. 
GullRaDriel
Member #3,861
September 2003

Maybe because the Z position is now too near of the screen and part of what's drawn got eaten. If your faces are like 'flashing' when turning the object, it's because the point of each faces are not clockwise/counter clockwise ordered. Edited "Code is like shit  it only smells if it is not yours" 
