User-Assisted Mesh Simplification

Download Page:

http://cggmwww.csie.nctu.edu.tw/research/index.php?research=mesh

Presentation Slides( for my Master Defense):

http://yuying.tw.googlepages.com/0830.pdf

Highlight:

A novel approach for user to precisely increase the vertex resolution of desired regions on the simplified mesh, while preserving the global vertex count:

Algorithm Summary:

1. Generate a Progressive Mesh (PM) for the model: a continuous sequence of edge collages that will gradually reduce the model to only 1 vertices.
2. In the PM, locate all edge collapse pairs on the target region to be refined, denoted as eg.
3. Specify the desired global vertex count after simplification, denoted as g.
4. Specify the desired vertex count for the target region after simplification, denoted as x.
5. Identify ecX, which is the marginal edge collapse that will immediately reduce the target region to x vertices.
6. Exchange the order of ecX with the (g+1)-th edge collapse of PM, making it the new (g+1)-th edge collapse of PM.
7. Linearly reallocate the execution order of all other edge collapses of eg to preserve the original order of eg.
8. As a result, the target region will have x vertices after simplification.

Result:

User can precisely allocate more vertices to regions of interest on a simplified mesh.

Note:

This paper is primarily based on my Master thesis paper. Mr. Ho, a senior PhD. student of my lab, helped re-organized and submitting this paper.

The Joy of an Entrepreneurial Venture

MyTaxi (http://www.mytaxi.tw/) , the startup company co-founded by my wife and me, have just officially launched in early January. The primary goal of our company is to offer an enjoyable and economic alternative for commuters in Taipei: taxi-sharing. Within just one month, our website have accumulated hundreds of registered users and tens of effective routes. We also plan to promote our services to companies, schools and organizations as monthly packages, similar to what Zimride did.

To my wife, this endeavor is her entrepreneurial dream came true, and it is critical in building the prerequisite of pursuing MBA in entrepreneurship: she have already got an offer from Babson (ranked #1 in entrepreneurship), with a scholarship.

To me, it is an truly exciting challenge.

As a software engineer with 10+ years of experience of C/C++/Java programming, mainly for Windows-based 3D, video navigation and cryptography applications, it is very interesting and rewarding to engage myself in something quite different: website developments.

Our website is developed in PHP with MySQL, Java Script (JQuery) and some CSS. It is deployed under the CodeIgniter framework, an open source, elegant, compact and well-documented web framework that I totally acclaims.

In my opinion, PHP programming is quite different to the "traditional" C/C++ counterpart: no compiling, no type-castings, no memory managements, no crashes (at least I haven't encountered...), no multi-threading, no printf/ostream/CString/OutputDebugStringW mess. The learning curve is almost non-existent. I love it! But it will be more beautiful if there exists an orthodox IDE for PHP (like VisualStudio to C/C++ and Ellipse to Java).

I had experience in Java Script programming while developing the HDi scripting engine for HD DVD Advanced Content players, so developing user-side features for our website (ex: hovering text) by Java Script isn't a challenge to me. In addition, I love the JQuery library! It makes programming Java Script like talking with an intelligent alien, instead of a stupid one.

In conclusion, I just feel lucky in choosing the career of a software engineer. The shinny new things never stop to show up (I am experiencing with Maya's Pymel, and Blender's Python scripting languages, and I will deploy our website into hand-held device friendly formats after the current one is stable enough).

Finally, thank you for your reading!

Current Studying Activities

This page organize my current studying activities. Comments welcome!

*. Mesh Parameterization and Optimization. Currently I am collaborating with my (previous) advisor Prof. Jung Hong Chuang at NCTU on projects related to shape correspondence. I am responsible for solving problems related to mesh parameterization and hence, using packages to solve optimization problems.

• CirclePatterns, http://www.multires.caltech.edu/software/CircleParam/html/index.html. The source code demonstrates Circle Pattern, an algorithm for finding discrete conformal (angle-preserving) parameterization. Wonderfully, it also demonstrate how to use MOSEK, a powerful optimization software that is capable of solving linear, quadratic (convex), conic and even general non-linear convex problems.
• Following the author's instructions, I have implemented the spherical parameterization part. The task requires solving a general non-linear problem (minimizing the energy term). I have implemented C++ codes to use MOSEK to solve the problem, which involves providing functional, gradient and Hessian evaluations to MOSEK's interior-point solver. While the problem is solved for some simple models, unfortunately the problem seems to become non-convex for some complex models; MOSEK simply halts when it detects the Hessian to become not positive semidefinite, ending up with suboptimal solution.

1. Techniques on generating/extruding architectural drawings (e.g. floor plans) into 3D models.

• Convex Optimization, Stephen Boyd and Lieven Vandenberghe / http://www.stanford.edu/~boyd/cvxbook/ (70% up to chap9: Unconstrained Minimization)
• Procedural House Generation: A method for dynamically generating floor plans, J. Martin UNC, i3D2006 (100%)
• Generating 3D Building Models from Architectural Drawings: A Survery / http://www.public.asu.edu/~pwonka/Publications/publications.html (40%)
• MIT "BUILD" system: A tool for maintaining consistency in modular systems. Said to be utilized as a tool of generating floor plans to for specific purposes (e.g. hospitals). / http://dspace.mit.edu/handle/1721.1/6909 (10%)
• ArchiDNA(a fractal-like design CAAD system) http://dmg.caup.washington.edu/xmlSiteEngine/browsers/static/project72.html

2. Crowd / traffic simulation techniques. Exploit their applications into urban model synthesis.

• Virtualized Traffic / http://gamma.cs.unc.edu/TRAFFIC_RECON/ (100%)
• Dense Crowd Simulation / http://gamma.cs.unc.edu/DenseCrowds/ (25%)
• City-Scale Urban Environment Synthesis http://wiki.cs.purdue.edu/cgvlab/doku.php?id=projects:urban (100%)
• Procedural Street Modeling / http://www.public.asu.edu/~pwonka/Publications/publications.html (20%)

3. Computational Geometry for Architecture

• Prof. Potmann's research / http://www.geometrie.tuwien.ac.at/pottmann/ (25%)
• "Architectural Geometry" / http://www.architecturalgeometry.at/ (10%)
• "Discovering Structural Regularity in 3D Geometry", http://www.geometrie.tuwien.ac.at/pottmann/2008/discovering08/discovering.html (10%)
• "Algorithmic Architecture" by Harvard Architecture Prof. Kostas Terzidis / http://www.amazon.com/Algorithmic-Architecture-Kostas-Terzidis/dp/0750667257/ref=ntt_at_ep_dpi_1 (100% - very interesting!)
• "Expressive Form: A Conceptual Approach to Computational Design " by Prof. Kostas Terzidis / http://www.amazon.com/Expressive-Form-Conceptual-Approach-Computational/dp/0415317444/ref=ntt_at_ep_dpi_3 (90%)
• Model Synthesis (a good, general-purpose procedural modeling algorithm) / http://gamma.cs.unc.edu/synthesis/ (80% Implementing this by Pymel in Maya)
• Pamphlet Architecture 27: Tooling by Benjamin Aranda and Chris Lasch / http://www.amazon.com/Pamphlet-Architecture-27-Benjamin-Aranda/dp/1568985479 (80% -some innovative, experimental ways to apply basic computing techniques, e.g. fractal and crowd simulation into architectural modeling)

4. Global Illumination (hopefully it can be applied in solving lighting analysis problems in architecture)

• VRay introduction (and some information on GI algorithms) in Chinese: http://hammerbchen.blogspot.com/2008/05/vrays-global-illumination-gi-methods.html (90%)
• Some excellent research on lighting analysis by a Computer Graphics professor: http://www.cs.rpi.edu/~cutler/ (80%)
• Study lectures on GI: http://www.cs.rpi.edu/~cutler/classes/advancedgraphics/S09/lectures/ (10%)
• DIALux / http://www.dialux.com/ (80%)

5. Cool Architecture Stuff

• A movable, multi-purpose architecture project by Architecture Prof. http://www.youtube.com/watch?v=NcTRFlhMlhk (100%)
• A New Zealand based architecture firm evolving architecture through computation http://www.nzarchitecture.com/blog/ (lots of links to "Generative Design" materials, great!)
• "De architectura libri decem" (中文版: 建築十書), Marcus Vitruvius Pollio. http://en.wikipedia.org/wiki/De_architectura (40%, to book 4)
• Digital Urban Blog http://www.digitalurban.blogspot.com/ , a blog hosted by Centre for Advanced Spatial Analysis, UCL. Also contains information about CAAD studies in ETH in Zurich. Emphasizing on applications of procedural modeling of cities. And some easy (from the perspective of a CS student) but interesting stuffs.
• "Cities for a small planet", Richard Rogers.

GPU Programming Studies

I have done some research on GPU programming by the request of my graduate school advisor. Here are some study reports on several applications of GPU programming:

"Hardware-Assisted Computation of Depth Contours" by S. Kirshnan et al.
Report.

"Extended intersection queries on a geometric SIMD machine model" by S. Kirshnan et al.
Report.

"Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid" by J. Bolz et al.
Report.

I have also made a report on vertex shader, pixel shader and shading languages.
Report.

Highlight: