Grain of Salt - Speeding up OpenGL (lisp rant) [entries|archive|friends|userinfo]
snauts

[ userinfo | sc userinfo ]
[ archive | journal archive ]

Speeding up OpenGL (lisp rant) [Mar. 25th, 2009|12:05 pm]
Previous Entry Add to Memories Tell A Friend Next Entry

Consider simple C pseudocode for displaying OpenGL object:
struct Point {
    float x, y, z;
};

struct Triange {
    Point *a, *b, *c;
};

struct Object {
    unsigned count;
    Triangle *mesh;
};

void displayPoint(Point *p) {
    glVertex3f(p->x, p->y, p->z);
}

void displayTriangle(Triangle *t) {
    glBegin(GL_TRIANGLES);
    displayPoint(t->a);
    displayPoint(t->b);
    displayPoint(t->c);
    glEnd();
}

void displayObject(Object *o) {
    unsigned i;
    for (i = 0; i < o->count; i++) {
	displayTriangle(&o->mesh[i]);
    }
}

Similar code written in lisp could look like this:
(defstruct point x y z)
(defstruct triangle a b c)
(defstruct object mesh)

(defun display-point (p)
  (vertex-3f (point-x p) (point-y p) (point-z p)))

(defun display-triangle (tr)
  (begin +triangles+)
  (display-point (triangle-a tr))
  (display-point (triangle-b tr))
  (display-point (triangle-c tr))
  (end))

(defun display-object (o)
  (mapc #'display-triangle (object-mesh o)))

Such C code should be faster than lisp code, but consider that in both of these examples 3D object is stored in memory as some data structure that must be accessed every time you want to draw object. Usually about 30 times per second. Imagine if time used for data access could be saved. What I mean by that is idea of keeping objects as functions not as data structures. For example:
displayObject(fish);

Could be translated in:
displayFish();

void displayFish(void) {
    glBegin(GL_TRIANGLES);
    glVertex3f(1.0, 2.0, 3.0);
    glVertex3f(0.0, 0.0, 0.0);
    glVertex3f(0.5, 0.5, 1.2);
    glEnd();
    glBegin(GL_TRIANGLES);
    glVertex3f(1.0, 0.9, 4.0);
    glVertex3f(1.0, 2.0, 3.0);
    glVertex3f(0.0, 0.0, 0.0);
    glEnd();
    glBegin(GL_TRIANGLES);
    glVertex3f(0.5, 0.5, 1.2);
    glVertex3f(0.0, 0.0, 0.0);
    glVertex3f(1.0, 0.9, 4.0);
    glEnd();
}


It looks quite complicated task in C (but not impossible), while in lisp such thing could be done quite easily:

(defstruct point x y z)
(defstruct triangle a b c)
(defstruct object mesh)

(defun compile-point (p)
  `(vertex-3f ,(point-x p) ,(point-y p) ,(point-z p)))

(defun compile-triangle (tr)
  `((begin +triangles+)
    ,(compile-point (triangle-a tr))
    ,(compile-point (triangle-b tr))
    ,(compile-point (triangle-c tr))
    (end)))

(defun mappend (fn list)
  (apply #'append (mapcar fn list)))

(defun compile-object (o)
  `(lambda ()
     ,@(mappend #'compile-triangle (object-mesh o))))

Now when I try to execute:
(setf *p1* (make-point :x 1.0 :y 2.0 :z 3.0))
(setf *p2* (make-point :x 0.0 :y 0.0 :z 0.0))
(setf *p3* (make-point :x 0.5 :y 0.5 :z 1.2))
(setf *p4* (make-point :x 1.0 :y 9.0 :z 4.0))

(compile-object
 (make-object :mesh (list (make-triangle :a *p1* :b *p2* :c *p3*)
			  (make-triangle :a *p4* :b *p1* :c *p2*)
			  (make-triangle :a *p3* :b *p2* :c *p4*))))

I get my 3D object "embedded" in lisp code:
(LAMBDA NIL
 (BEGIN +TRIANGLES+)
 (VERTEX-3F 1.0 2.0 3.0)
 (VERTEX-3F 0.0 0.0 0.0)
 (VERTEX-3F 0.5 0.5 1.2)
 (END)
 (BEGIN +TRIANGLES+)
 (VERTEX-3F 1.0 9.0 4.0)
 (VERTEX-3F 1.0 2.0 3.0)
 (VERTEX-3F 0.0 0.0 0.0)
 (END)
 (BEGIN +TRIANGLES+)
 (VERTEX-3F 0.5 0.5 1.2)
 (VERTEX-3F 0.0 0.0 0.0)
 (VERTEX-3F 1.0 9.0 4.0)
 (END))

P.S. Technically it would be right to change compile-object into:
(defun compile-object (o)
  (compile nil `(lambda ()
		  ,@(mappend #'compile-triangle (object-mesh o)))))

linkpost comment

Comments:
[User Picture]
From:[info]barvins
Date:March 25th, 2009 - 04:16 pm
(Link)
Cik saprotu, visos gadījumos procesoram ir jānolasa no atmiņas konkrētas koordinātas, kurās parādīt trīsstūri. Tikai pirmajā gadījumā ķēdīte ir garāka - vispirms nolasa adresi (pointeri), kurā atrodas koordināta, un tad tikai pašu koordinātu.
Starpība starp lispu un c tad būtu tāda, ka lispā var rantaimā veikt optimizācijas, t.i., iebliezt datus kodā kā konstantes, bet c to var tikai ar rociņām hārdkodēt pirms kompilēšanas.
By the way, dažos gadījumos c kompilators ir spējīgs noņemt "abstrakcijas radīto sarežģītību", t.i., atrullēt ciklus vai aizvākt datu atrašanu caur pointeriem, ja dati ir konstanti.
[User Picture]
From:[info]snauts
Date:March 25th, 2009 - 04:31 pm
(Link)
Tu pareizi saprati, bet kāpēc uzreiz "ar rociņām hārdkodēt", tu jau vari uzrakstīt progu, kas tavu 3D objekta failu pārtaisīs par C sourci, kuru tu pēc tam vari savai progai piekompilēt. BTW Gudri vīri man jau lika nokaunēties, jo šāda fīča ir jau iekš OpenGL 1.1, kur komandas netiek izpildītas, bet gan nokompilētas un sabāztas video kartē, kas ir vēl krutāk.