2008年9月17日星期三

Laplacian Smoothing 拉普拉斯平滑

Question: if I do laplacian smoothing to a model many many many times, what happen???

上面的图是对horse模型的不断平滑结果,结果是收敛为一点(这个图没有贴上来,上面的图已经足够看到这个trend了)!!!
Reference: Skeleton Extraction by Mesh Contraction. ACM TOC 2008.
"Laplacian Smoothing that moves vertices along their approximation curvature normal directions. Note that an unconstrained normal flow of the vertices would progressively smooth out all the details of the model and converge into a single point."

Interpolaton Loop Subdivision Surface

mentor好像对此有兴趣,所以暑假实习期间我就实现了这个文章,效果如下,可惜当时没有跟用于插值的Butterfly subdivision做比较。





Reference:
Interpolation by geometric algorithm. Takashi Maekawa, etc. 2006.

2008年9月11日星期四

Metaballs

第一次听到这个概念是关于一个叫spore的游戏。

Gamedev近来有一片介绍metoball的文章 Exploring Metaballs and Isosurfaces in 2D

2008年8月21日星期四

How to Draw Bezier, B spline, patch, or Subdivision Surface using OpenGL?

Conception:
http://groups.csail.mit.edu/graphics/classes/6.837/F04/lectures/16_curves_surfaces.pdf
Explain what is Bezier, B-spline(=uniform cubic BSpline, 是rational的), NURBS(=Non-Uniform Rational BSpline). 直观地,只考虑4个顶点的,order = 4,degree = order -1 = 3,Bezier curve是插值头尾两个控制点的,而且每递增3个新控制点才新产生一段curve,之后两端curve的接缝点只是几何坐标值相等,但是切向tangent却不连续;相比之下,Bspline curve并不插值首位两个顶点,每递增1个新控制点就产生一段curve,前后两端curve连续并且切向一直。
Q(t) = GBT(t) = Geometry(4*1 vector of four control points) * Spline Basic (4*4 matrix) * Power Basic([t^3, t^2, t, 0]).
它很绚的作业在http://groups.csail.mit.edu/graphics/classes/6.837/F04/assignments/assignment8/

OpenGL FAQ, 19.010 How can I use OpenGL evaluators to create a B-spline surface?
OpenGL evaluators use a Bezier basis. To render a surface using any other basis, such as B-spline, you must convert your control points to a Bezier basis. The OpenGL Programming Guide, Chapter 12, lists a number of reference books that cover the math behind these conversions.

首先,OpenGL/glu使用的evaluater是直接提供Bezier curve/NURBS的支持,但是B-spline就没有啦。结果是,B-spline curve都要转成Bezier curve来画啦。可以参考E.Angel's curves.c这例子。

E. Angel, Interactive Computer Graphics , A Top-Down Approach with OpenGL, Third Edition Addison-Wesley Longman, 2003. 这书上有一个curves.c的可运行例子,可以画Bezier,b-spline 以及interpolation curve,不错的。OpenGL虽然内部只支持Bezier但是由于b-spline与Bezier相互间可以转换,因此,用户给出b-spline控制点要画cure时候,我们就求要画同样一段curve用Bezier控制点的话这些Bezier控制点的坐标是什么呢?求出这些Bezier控制点坐标之后,这段curve就可以用OpenGL的evaluater来画了。E.Angel's curves.c例子就是利用了同一段curve可以用Bezier控制点来得到,也可以用b-spline控制点来得到。

http://www.itee.uq.edu.au/~comp4201/Curves6.pdf
这个ppt(curve and surface in OpenGL)里面不是介绍曲线的数学表达式,而是实际上怎样用
glMap1f(GL_MAP1_VERTEX_3, 0.0, 1.0, 3, 4, &newcpts[0][0]);
glMapGrid1f(30, 0.0, 1.0);
glEvalMesh1(GL_LINE, 0, 30);这些具体画curve的函数.


http://www.dgp.toronto.edu/~hertzman/stroke/
里面的代码是在painterly rendering papers to draw brush strokes in OpenGL,除了画Bezier和Bspline curve之后还有一些NPR的资料以及siggraph 02的course note。

Google Code, search Bspline.

2008年8月18日星期一

OpenGL Transformation

Modelview(Modeling and Viewing) Transformation:

“First of all, telling about the order of matrices in a matrix product is senseless as long as nothing was said about using either column or row vectors. OpenGL uses column vectors, while D3D uses row vectors.” 这是必须先明确的,OpenGL中 v_new = M * v_old, where M is 4*4, and v_new , v_old is 4*1.

仔细阅读红宝书第三章(http://www.glprogramming.com/red/chapter03.html)里面介绍了可以从两个角度来看待矩阵变换次序。

首先,OpenGL中维护一个C is current modelview matrix. All viewing and modeling transformations are represented as 4*4 matrices, 用M表示。之后无论是直接用glMultMatrix*() or transformation command(glT/R/S) 其实就是将变换矩阵M后乘当前的C矩阵得到C*M,
然后在v' = C*M*v.

利用红宝书中的例子:
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glMultMatrixf(N); /* apply transformation N */
glMultMatrixf(M); /* apply transformation M */
glMultMatrixf(L); /* apply transformation L */
glBegin(GL_POINTS);
glVertex3f(v); /* draw transformed vertex v */
glEnd();
先将C设置I, C' = CNML, v' = C'v = INMLv.
这个理解一般没有异议,解决了code顺序与矩阵乘法次序概念上问题。
也就是说如果你都写好了code,叫我将矩阵写出来当然没有问题;反过来,你给出里NML,让我将code写出来,这也好办。
但是,从用户/写代码的人来看,当我需要将一个object/vertex怎么变怎么变,又不知道具体的矩阵M,我怎么做呢?

关键要理解glTranslate*, and glRotate*的次序,红宝书中那先旋转还是先平移的例子要好好看。

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glMultMatrixf(T); /* translation */
glMultMatrixf(R); /* rotation */
draw_the_object();

1. "fixed coordinate system - in which matrix multiplications affect the position, orientation, and scaling of your model - you have to think of the multiplications as occurring in the opposite order from how they appear in the code. "
从一个固定的全局的,可以理解为世界坐标来看的话,代码从后往前考虑,NMLv是L, M, N依次作用于v。这个"your model"为什么呢?书中的意思是从固定的这坐标系来看待时候,不要考虑你的物体坐标,反正我就是影响你这个物体的每一个点在我这个固定坐标里面的位置。
上面例子从固定的世界坐标来看的话,物体先被绕着固定世界坐标系的原点旋转,再沿着世界坐标系来平移,根本不用考虑什么物体坐标系。

2. “Another way to view matrix multiplications is to forget about a grand, fixed coordinate system in which your model is transformed and instead imagine that a local coordinate system is tied to the object you're drawing. All operations occur relative to this changing coordinate system. With this approach, the matrix multiplications now appear in the natural order in the code. (Regardless of which analogy you're using, the code is the same, but how you think about it differs.) ”
物体的局部坐标系来看,有一个物体本身的坐标系跟物体本身绑定在一起,所有变换都会作用于这个物体的坐标系(同时由于物体是对于这个自己的坐标系来说的,所以物体跟着自己局部坐标系也被变换了)。
于是上面的例子中,物体的坐标系先被平移了,然后物体的坐标系绕着自己的原点来旋转。整个过程当中,世界坐标依然没有变,而且物体一直跟着自己的物体坐标系变化。 对于想树形结构的物体,如机械人,太阳系,红宝书的建议是从局部坐标来看。

========
上面的问题弄清楚就看为什么人家常说要先做scale, then rotate, translate last呢?
v' = T*R*S*v
从全局的角度来看(也就是从后往前看),先做scale的话,scale之后的3个轴还是与scale之前的方向一样,虽然长度变了,但这不影响下面的Rotation变换。
从局部物体角度来看(也就是从前往后看),物体本身的坐标先做旋转,物体也跟着旋转了,之后的缩放,物体的坐标系会被缩放,连带物体也一样。

========


注意:
glRotate*(angle, xAxis, yAxis, zAxis), 其中轴(xAxis, yAxis, zAxis)是通过original的unit vector。


http://csc.csudh.edu/jhan/Fall2006/csc461/CourseNotes/CSC461-Lecture16.ppt
http://www.juniata.edu/faculty/rhodes/graphics/opengltrans.htm
http://www.cs.unm.edu/~angel/CS433/LECTURES/CS433_13.pdf 上面三个链接其内容几乎一样的,看这个就可以了。

http://pages.cs.wisc.edu/~psilord/docs/local_axis.html 难懂
http://www.songho.ca/opengl/gl_transform.html OpenGL Transformation. 从math上介绍geometry pipline上的变换矩阵,很好.

OpenGL, GLSL Tutorial

Immediate mode -> VBO
Light, Texture -> shader
-------------------------------------------------------------------------------
OpenGL tutorial
红宝书,
http://www.codecolony.de/ 一些入门的例子。

GLSL
橙色书 OpenGL Shading Language 最快最明了的学习资料,
http://www.opengl.org/sdk/docs/tutorials/TyphoonLabs/ PDF文档。
http://nehe.gamedev.net/data/articles/article.asp?article=21 NEHE21课对glsl的基本概念简介。
http://www.clockworkcoders.com/oglsl/tutorials.html 入门例子, 里面有一个libglsl的库帮助使用glsl,看来这是趋势,这样就没有必要每次都自己来compile和link那shader了。
http://appsrv.cse.cuhk.edu.hk/~ymxie/Geometry_Shader/ 几何shader的简介。
http://cirl.missouri.edu/gpu/ 一个几何shander的例子。

Tools, Shader Maker
http://cg.in.tu-clausthal.de/publications.shtml#shader_maker
(里面还有些有趣的论文)。
(1)这个工具很适合入门,它将shader的载入编译以及链接都集成了,用户只需要将网上的vertex /geometry/fragment shader直接黏贴上前,F5就可以看到效果啦。
(2)被作用于shader的mesh是可以从外部载入的,虽然它本身提供了如cube,sphere, torus这里经典模型。这样的好处是,我自己的mesh processing算法对mesh处理之后,放入这里,然后从网上找些shader,就可以看到一些比较不错的render效果了:-)

NVIDIA
http://developer.nvidia.com/object/sdk_home.html
nvMath, nvImage, nvModel, nvWidgets,
使用GLEW, png & zlib, 怎么使用nv对gl的extension,
有一个uvShaderUtils.h来帮助使用GLSL.
实现了旋转,缩放,移动模型的操作。
======================

Vectex Buffer Object

红宝书中有一节关于"缓冲区对象中的顶点数组"。

OpenGL VBOs specification. VBO is based on the vertex array(which has three steps:enable/define/draw array). 将array data放到server side, 并可以通过mapping得到buffer object的指针进而修改server side那边的data. 最后带有Usage Examples.

http://www.spec.org/gwpg/gpc.static/vbo_whitepaper.html

“VBOs are intended to enhance the capabilities of OpenGL by providing many of the benefits of immediate mode, display lists and vertex arrays, while avoiding some of the limitations. ”

http://developer.nvidia.com/object/using_VBOs.html

2008年7月26日星期六

Reading. About GPUs.

1. How GPUs work. David Luebke(Nvidia research), Greg Humphreys(University of Virginia)
http://www.cs.virginia.edu/~gfx/papers/paper.php?paper_id=59
其中D.Luebke名字挺熟悉的,查查看原来是A Developer's Survey of Polygonal Simplification Algorithms的作者:-)
他的blog上说"On July 24, 2006 I left academia to help start a research group at NVIDIA Corporation", 然后我再看看他的papers介绍,原来他是以做simplification开始的,在Lod方向也许多工作,之后是rendering以及gpu。从academia到corporation,之前的H.Hoppe加入MS也是,没有记错的话做细分的D.zorin加入Pixar....都是idol啊

2. how gpu works.
http://c0de517e.blogspot.com/2008/04/gpu-part-1.html
http://c0de517e.blogspot.com/2008/04/how-gpu-works-part-2.html
http://c0de517e.blogspot.com/2008/04/how-gpu-works-part-3.html
作者的另一个文章http://c0de517e.blogspot.com/2008/06/begin-here.html也是很好的:
do it for fun.
Don't EVER think to know enough. You don't. If you've been programming for 4-5 years and took a 5 years university course, then you will have just the basics that are required to be able to understand almost anything, with some effort. They give you only the alphabet, from there on, there is the real knowledge! That's the single most important advice I can give you.

最后,要是哪位朋友有下面的书,不知是否可以借阅:-)
Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry (The Morgan Kaufmann Series in Computer Graphics) (Hardcover)by Leo Dorst (Author), Daniel Fontijne (Author), Stephen Mann (Author)
Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (Hardcover)by Christer Ericson (Author)

2008年4月27日星期日

Problem. Evaluation of Hoppe94 Loop Subdivision Surfaces

Given a point P(k, v, w) in the initial control mesh, where k is the triangle index, (v, w) is the corresponding barycentric coordiants(u+v+w=1). What is it posiition on the limint surface?

Papers give use the answer:
[1] J.Stam. Exact evaluation of catmull-clark subdivision surfaces at arbitrary parameter values. 1998.
[2] J.Stam. Evaluation of Loop Subdivision Surfaces.
I have implemented the [2], which is a trivial job, for most data (I use the lpdata50Nt.dat) can be downloaded from J.Stam's webpage.
However, if the loop masks are changed, for example, the h.hoppe97, then Stam98's evaluation method and data can not be used directly, because he did not take the feature types into consideration. So.... a big question, i'm still strugglling with it:-)
[3] Denis Zorin.Evaluation of Piecewise Smooth Subdivision Surfaces.2002

Hoppe 1994. Improved Loop Subdivision

经典的Loop87版本,是对Box-Spline(这我也不懂)的扩展,是没有考虑feature type的。

H.Hoppe94版本的Loop模式在对顶点的特征类型进行分类基础上,对不同的顶点类型(smooth, dart, crease, corner)使用不同的masks。

2008年4月16日星期三

Paper reading: Mesh Deformation

现在我自己的工作倒是和mesh deformation没有关系,我在做subdivision surface fitting。However,montor好像有意在这方面做点东西,于是,我也偶尔看点这方面的paper。现在我希望有时间简略整理一下自己看过的,或者有点感觉的东西。
1. Multiresolution deformation
多分率,细节保持的变形。在某一层的变形基础上加上细节。怎么表示细节是一个问题。最简单的就是每一个顶点加一个法相位移。这方面的工作在2000左右热。可以看normal meshes, displace subdivision surfaces,这都是模型的另一种表示方式。
2. Laplace deformation
细节保持的变形,是基于微分空间的变形,就是在微分空间中表示变形。这方面类似的还有gradiant 能量函数,和possion能量函数这些变形方法。siggraph2004热的。
3. Deformation transfor
Deformation transfer for triangle meshes_sig04.Robert W.Sumner
将A模型的变化,转移到B模型,使得B模型也发生类似于A模型的变化。

2008年4月5日星期六

Mesh Parameterization

网格参数化的分类。根据base domain是否是平面可以分为平面的参数化和非平面的参数化方法。
而平面参数化方法,被参数化的网格必须有边界,进一步根据其边界在参数化时候是固定的还是自由的,分为固定边界方法和自由边界方法。具体的细节可以参考2007年siggraph course note的相关文章。


而我现在实现是Lee98的MAPS方法,将原网格一步一步递进的参数化都一个3D的base domain上。这个base domain是对origianl mesh的simplification的结果。现在的问题是怎么保证参数化结果里面没有triangle 的flipping和reduce 参数化的distortion。

Reference:
Lee98. MAPS: Multiresolution Adaptive Parameterization of Surfaces.