Introduction to Look-up tables
Back in the DOS era and 80×86 CPU (I guess it’s quite old), mathematical operations for 3D Graphics were too expensive. One of the tricks to speed-up the graphics pipeline was using a pre-computed trigonometric functions implemented in a table. The benefit of using discretization of function parameter is measured by how complex the computation of function relative to accessing a table using a discretized input parameter. This method of replacing function call into looking up a table for already computed values are generally called Memoization.
Generalizing Look-up table for higher dimension
In previous example(trigonometric function) the input parameter is only one. If we think the parameter as a dimension, then the domain of the input parameter is a one dimensional object (a line). Of course the memoization technique is not only limited to one dimensional look-up table but can also be generalized to higher dimensions. In 3D Graphics (again), The memoization for higher dimension is used in texture mapping (2D) or voxel(volume pixel) representation for object modeling.
Grid shift: LUT in Coordinate transformation
Now let’s move from 3D Graphics to another area. In Geospatial domain, the same technique (look-up table) is used to transform coordinate from one Coordinate Reference System (CRS) to another CRS. Since most geographical coordinates only has two horizontal components (latitude and longitude). The look-up table is in the form of a two-dimensional grid. This grid-based transformation is also known as ‘Grid Shifts’.
It’s been quite a while since my last post about Google Summer of code activities. I was trying to understand the inner working of the library which I use and gathering deeper knowledge about spatial coordinate and mapping. As I may previously mentioned in earlier post, I am working with GDAL and PROJ.4 Library. GDAL/OGR is mainly used for supporting many raster/vector format and also dealing with WKT (Well Known Text) representation of coordinate system. The Coordinate system is defined in WKT Format although in the GDAL/OGR Library, the main coordinate system transformation is done in the PROJ.4 library which is wrapped through an interface which consists of OGRSpatialReference and OGRCoordinateTransformation.
Hello world! This is my first post about GSoC. I usually write post to this blog using Indonesian language so people who are from Indonesia can easily understand and also to contribute to probably technical corpora which is written in Indonesian. For the next posts that will be using gsoc2013 tag also will be written in English.
Now, a little bit of background won’t hurt.
This is my first experience in Google Summer of Code, applying and being accepted. My last status as student was 2010 which is almost three years ago. Now that I am back as student, I am eligible to apply as participant. Yay!
The project I am working on is under the organization of Computational Science and Engineering of Vienna University of Technology. Altough I am also a student in TU Wien, The Mentors are from different institute. My Mentors are from Department of Geodesy and Geoinformation. The project itself is implementing transformation algorithm for vertical datums. For me, this is something that is quite new. I did projects using spatial data before, but the inner working of the knowledge behind that was actually done by another person which background is geodesy. Well, the availability of libraries like PROJ.4, GDAL/OGR really helped me a lot back then. That’s why I thought this might be the way I can contribute back.
Fungsi logaritma merupakan fungsi yang termasuk lambat, bahkan dibanding dengan trigonometri (CMIIW). Beberapa waktu yang lalu yang terjebak dalam persoalan yang seringkali memanggil fungsi logaritma khususnya log10 untuk setiap iterasi. walaupun sudah mengurangi pemanggilan dengan memanfaatkan variabel, namun tetap saja program berjalan lambat. Akhirnya setelah bertanya dan mencari-cari, ada yang membuat implementasi fungsi logaritma yang lebih cepat dan tetap dalam batas error yang bisa diterima (1e-6). Idenya adalah membuat look-up table dari bit mantissa yang sudah dikuantisasi (di kliping) sehingga ukuran LUT-nya cukup kecil (implementasi yang saya buat hanya berukuran 256K) yang menurut penulis aslinya cukup untuk disimpan di dalam cache CPU.
Tulisan ini merupakan lanjut eksplorasi tentang inference engine seperti posting saya pada situs gamedev-Id tentang Simple Inference Engine in C++ dan di blog saya di pebbie.net. karena modul mesin inferensi ini digunakan pada tugas akhir saya tentang behavioral animation dengan menggunakan model berbasis kaidah (rule).