Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 22 May 2004
Offline Last Active Apr 24 2016 11:45 AM

Topics I've Started

An Exact Algorithm for Finding Minimum Oriented Bounding Boxes

01 June 2015 - 07:01 PM



I'd like to present a research paper that I worked on earlier this year. It relates to a common problem in game/graphics dev so it might be useful to some of you guys as well.


In short: I have implemented a new algorithm for finding tight-fitting enclosing OBBs for 3D meshes. For suitably "nice" inputs, it runs in O(n * sqrt(n) * log^2(n)) time compared to previous best O(n^3) from O'Rourke. For degenerate/adversarial inputs, it runs in worst case O(n^3 * log n) time. A formal proof of the optimality of this new algorithm is unfortunately beyond reach, but for all tested cases, the algorithm has been able to find the optimal minimum volume OBB.


Find the links here:

I hope you find this interesting and useful!

Computing an extreme point of a convex polyhedron faster than linear time?

26 December 2014 - 01:11 PM

Hi there, and happy holidays,


given a convex polyhedron (represented as a point soup) and a normal direction vector n, it is possible to compute an extreme point (a supporting vertex) of the polyhedron to the direction of n by linearly iterating through all the vertices of the convex polyhedron, computing the dot product of each with n and picking the farthest one.


However, if one wants to go faster than linear, it's possible to compute a vertex neighbor adjacency data structure (one which gives for each vertex a list of its neighboring vertices), and perform a graph search on that adjacency data structure using a greedy climbing method, i.e. start with an arbitrary vertex, and keep moving to its nearest neighbor that is more to the direction of the vector n. This works (although in practice one has to keep an eye out for plateaus due to potential numerical float imprecision issues), and it's something that I've been happily doing for a good while now. However, I'm now looking for a book, journal, article, conference or some other kind of reference to this method. Does anyone know of one? Also, what is the time complexity of that method? It is well faster than linear, and somehow I've always taken it as a O(logN) method, but now thinking about this, O(sqrt(N)) starts to feel more appropriate (since on the limit, it's transforming a search over a sphere to a search over a circle).


If anyone knows what this method is called, and if there a proof of its complexity somewhere, please let me know!

ScummVM running on the web!

10 June 2013 - 09:27 AM




Games programmers here might be interested in this project I have been working on the past few weeks. Have a look here:







Emscripten is a compiler that compiles C/C++ code to JavaScript for running on the web. As a test/proof-of-concept of its maturity and applicability to C++ codebases that weren't originally designed for the web in mind, I had a go at porting the ScummVM codebase to HTML5 with it.


The maturity and robustness is commendable, and Emscripten has become a viable alternative to Flash and Native Client. I develop a graphics system called gfxapi, which targets both Emscripten and PNaCl targets. With GLES2 and EGL support, developing 3D graphics against Emscripten is very similar to developing 3D gaphics for Android. Also recently, Unreal Engine 3 was ported over to the web, which goes to show that Mozilla's approach has the capability to scale as well.


The technical details of the ScummVM port can be discussed at the Emscripten mailing list.


Enjoy! smile.png

Try Angelscript live!

08 December 2012 - 12:48 PM


here's something cool I wrote up this weekend. With your modern browser with WebGL enabled, visit this page: MathGeoLib live test site. It is a project consisting of a few parts:
  • Uses my native C++ graphics rendering engine gfxapi. Utilizes the emscripten compiler to deploy the application to HTML5.
  • Integrates Angelscript as the live scripting engine.
  • Uses my MathGeoLib library for scripting primitives and geometry manipulation.
  • Interop between C++ MathGeoLib classes and Angelscript is achieved using an automatic bindings generator based on juj/CodeStructure.
The application allows writing Angelscript live on a web page, and render stuff on the screen by using constructs from MathGeoLib and gfxapi. I really must congratulate Andreas Jönsson for the Angelscript project - it is a very fine piece of technology! I have previously written C++ - script bindings interop for MathGeoLib for QtScript and Javascript, and using Angelscript is the most mature, easist and convenient one of them to work with! I evaluated Python, Lua and Mono to replace my previous JavaScript-based scripting engines, but Angelscript is the king of the hill. The support for strong typing and ability to do value types with function and operator overloading is exactly what is needed for good interop and convenient games scripting, and something where the whole competition falls short :)

Compile C++ to JavaScript for Web Pages from Visual Studio?

26 April 2012 - 02:15 AM


I think some people here might be interested to know about my latest project, called vs-tool. It is a plugin for Visual Studio 2010 which enables the integration of external compiler/linker toolchains into VS. The hard work was done by Gavin Pugh, the author of vs-android, who developed a MSBuild task plugin to allow invoking GCC from VS. For vs-tool, the following toolchains are now supported:

- Build with MinGW: http://dl.dropbox.co...de/vs-mingw.png

Allows building Windows applications if you have installed the MinGW compiler.

- Build with llvm-clang: http://dl.dropbox.co...de/vs-clang.png

Allows compiling with the clang compiler. Note however, that clang does not yet fully support building windows applications, but I have tested that simple hello world code at least builds and runs ok.

- Build with Emscripten: http://dl.dropbox.co...ode/vs-emcc.png

Emscripten is a wonderfully geeky and absurd project, where LLVM bytecode is translated into executable .js for the web. This means one can compile C++ code directly into .js. The project is developed by Alon Zakai from Mozilla, find the homepage at https://github.com/k...emscripten/wiki , and a technical paper at https://raw.github.c.../docs/paper.pdf . The main motivation that had me start building vs-tool was to add support for Emscripten directly into Visual Studio, which is now working quite nicely (adding MinGW and Clang support was a bit of a side tour). Rather insanely, Emscripten supports translating GLES2 code directly into WebGL code, which allows me to work on converting my Android GLES2 engine directly for the web, from Visual Studio! This is so hackish, insane, fun, and crazy, at the same time.

The homepage for vs-tool is at github: https://github.com/juj/vs-tool

If you give it a go, let me know how it goes!