Canj's trail: 2011

2011年10月11日星期二

有一个难题，例如一个大的三角形里面随便画几个stroke，可能是相交的，怎么根据strokes来对这个三角形做三角剖分，得到的还是三角形，不包含多边形。

想一个算法来解决问题的过程（这些问题不是text book上有标准answer的）：先想/实现一个简单的情况，例如都没有相交(怎么判断相交?), 然后假如有某种相交，在原来实现的算法上加入一些cases，然后假如还有某种复杂的情况，在原来实现的算法上在加入一些cases.... (没有想到的某些情况，就留到bug了)....

1. 是一个渐进的过程。

2. 别老是想重写。

假如在假如某些cases or 想着想着想要重写，多半不是good idea，因为很可能重写之后包含了新的cases但遗漏了旧的cases.

假如在过了一段时间回来这codes fix bugs时候，想要重写，多半不是good idea，因为很可能连当初为什么那样写都想不清楚or想不齐所有旧的cases.

2011年8月29日星期一

怎么定义一个QuadTriMesh, 同时支持quad and triangle faces?

class QuadTriMesh : public BaseMesh {

public:

struct Face;

...

};

#define NIL uint(~0)

struct QuadTriMesh::Face {

unsigned int id;

unsigned int v[4];

bool isQuadFace() const { return v[3] != NIL; };

};

2011年8月23日星期二

- 养成习惯工作在早上就开始做，别看看新闻推到下午or晚上。

- 修改某mesh operation的错误时候最难最怕就是等为出错在哪些face/vertex/edge, 如果能在maya中建一些简单的模型来重现, 这就好办了。

- 不想改变的变量加const.

- 考虑函数里的指针加QScopedPointer<T> ...

- C++ Destructor: 1. 子类的destructor总会自动调用父类的destructor吗?

2. destructor里面除了需要delete pointers之外其它的变量呢?

- http://www.mikeash.com/pyblog/friday-qa-2011-01-04-practical-floating-point.html

http://altdevblogaday.com/2011/08/21/practical-flt-point-tricks/?utm_source=twitterfeed&utm_medium=twitter

-what is LLVM ?

- http://code.google.com/p/alembic/

http://www.cgsociety.org/index.php/CGSFeatures/siggraph2011#alembic_1.0

- OpenColorIO (OCIO) is a new open source project from Sony Pictures Imageworks (SPI), which they hope will soon be widely adopted across the Industry. SPI – it must be said, especially since Rod Bredow took the role of CTO, – has excelled at meeting the open source community head on and spearheading along with ILM (and their OpenEXR work) – some of the most impressive displays of industry co-operation we have seen in years, if not decades.

- http://advances.realtimerendering.com/s2011/ Advances in Real-Time Rendering in 3D Graphics and Games.

http://iryoku.com/aacourse/ ACM SIGGRAPH 2011 Course Filtering Approaches for Real-Time Anti-Aliasing

- http://fgiesen.wordpress.com/ A trip through the Graphics Pipeline 2011.

- John Carmack (ID_AA_Carmack) on Twitter: Reading "Infrastructure: the book of everything for the industrial landscape". Much respect to civil engineers!

2011年8月16日星期二

- "Low-pass filtering statistics",

- Eigen library (http://eigen.tuxfamily.org)

Eigen's Geometry module provides two different kinds of geometric transformations:

1. Abstract transformations, such as rotations (represented by angle and axis or by a quaternion), translations, scalings. These transformations are NOT represented as matrices, but you can nevertheless mix them with matrices and vectors in expressions, and convert them to matrices if you wish. 这种类型描述的都是Pure R/T/S.

2. Projective or affine transformation matrices 两种: see the Transform class. These are really matrices. 其实是Represents an homogeneous transformation in a N dimensional space.

例如这是一个affine transformation matrix的例子, 描述的是concatenation_of_any_transformations: Transform<float,3,Affine> t = Translation3f(p) * AngleAxisf(a,axis) * Scaling3f(s);

An affine transformation matrix M is shaped like this:

( linear translation )

( 0...0 1 ) // the last row can be assumed to be [0...0 1]

Note that for a projective transformation the last row can be anything, and then the interpretation of different parts might be sightly different.

Isometry if the transformation is only a concatenations of translations and rotations. (In Euclidean geometry, a rotation is an example of an isometry, a transformation that moves points without changing the distances between them. from wikipedia)

Transformation Types:

2D rotation from angle Rotation2D

3D rotation as an angle + normalized axis AngleAxis

"Finally Rotation2D and AngleAxis are mainly convenient types to create other rotation objects." These are two most simplest rotation types.

- 遇到一个bug. QA用的版本可以稳定重新，但是我就是不能重现，所以我怀疑daily build是不是包含了最新的code. 后来试了最近的check in也包含在daily build里面, 应该就不是没有包含最新code了。同事建议看看release 和 debug版本。果然release version可以重新 debug版本不可以重新. 一直跟踪发现原因一个数组值没有初始化, 在debug中被初始化为3452816845 也就是0xcdcdcdcd, 但在release下大部分是0.

- NVIDIA path render,

- 工作需要了解求Normal Map细节，于是读了NVIDIA mesh tool(http://code.google.com/p/nvidia-mesh-tools/)中NVMeshMender的实现, 知道了Tangent space的求法, 例如先根据uv求出TB然后假如N的时候考虑smoothgroup. NVIDIA的工具Melody虽然没有给出代码实现, 但可以玩玩normal map的生成.

- "State of the Art Report, Survey of Real-Time Tessellation & Geometry Synthesis Methods" 罗列了相关papers.

- http://www.lysator.liu.se/c/c-faq/c-1.html C-FAQ.

- Check the QScopedPointer for resource acquisition is initialization(RAII), and QSharedPointer for reference count.

2011年8月12日星期五

代码bug

昨天写代码犯了个错误：

子类override父类的virtual member function时候不需要写函数参数的default values。

2011年7月29日星期五

顶点边面数目的关系

今天看模型时候观察到了一个规律，原来这个规律还有理论支持。

2011年7月28日星期四

三角面local frame上的tangent

两个向量的夹角

2011年7月25日星期一

不同local frame之间的角度值

weekly update

- row-major vs. column-major, affine transform. some history, http://fgiesen.wordpress.com/2011/05/04/row-major-vs-column-major-and-gl-es .

- a trip through the graphics pipeline 2011, http://fgiesen.wordpress.com/2011/07/09/a-trip-through-the-graphics-pipeline-2011-index/

- "Obligatory FXAA Post", what is AA/MSAA/MLAA (doing AA as a post-process, depth based)/FXAA (post-process, luminosity based technique)? 例如对FXAA最好的理解是你之前尝试过了其他AA方法并知道有什么问题然后去看新技术是否克服了旧问题;// "Image Space for Beginners" Render a Quad with the texture you want to do sth on, shader code. A distortion example with code.// "Moving beyond the Linear Bezier" linear, quadratic and bezier curve equations. level of continuity C0/C1/..., how to obtain a piecewise bezier with C1 continuity(meaning that the first derivative is continuously defined), how to obtain a cubic beizer curve that has C2 continuity with deBoor points.// "Little more theory with your mesh", Euler Characteristic, Closure/Link/Star of simplicial complex. http://jonmanatee.blogspot.com/

- book [A New Kind Of Science by Stephen Wolfram, 2002].

- [Procedural Textures Mapping using Geodesic Distance 2011]

- from twitter, ID_AA_Carmack John Carmack "I would like to use reference and const object fields more, but it can require awkward dances in initialization lists." 复习了有两种东西需要在初始化列表中完成初始化的.

三角形法向 - 两个frame之间的angle

2011年7月20日星期三

叉积的方向

2011年7月16日星期六

weekly update

- What is the OpenGL Context look like? A structure in C? An object is attached to a target (a pointer in C), then the state machine use the target to get and set the value of the object? http://www.arcsynthesis.org/gltut/Basics/Intro%20What%20is%20OpenGL.html

- profiling. Mac上的shark比较流行，可惜在windows上没有.

Download Windows SDK, v7.1, to get the xperf application and play with it.

xperf http://msdn.microsoft.com/en-us/performance/cc825801.aspx and Process Explorer.

Debugging Tools for Windows (x64)

Microsoft Windows Performance Toolkit

Microsoft Windows SDK v7.1

a similar profiler from AMD http://developer.amd.com/tools/CodeAnalyst/Pages/default.aspx

- 继续看[Introduction to Linear Algebra]里面的subspace, column space, null space的概念。

Column space contains all the right hand sides, in which case the Ax = b is solvable. The Null space N(A) contains all the solutions of Ax = 0.

- 继续读[Scientific Computing: An Introductory Survey by Michael Heath]

1. 在书中解nonlinear equations system or optimization的例子时候终于知道跟linear system ( system of linear equations )的关系了, 用iterative methods解前者的问题时候每一步都迭代中很可能需要解一个线性方程组来得到下一步走向的信息. 例如在P158 5.2.3, Newton's Method for One dimension nonlinear equation: use a linear line to fit the curve at every step.

2. 怎么求解minimization of quadratic function/energy (which is quadratic object function without constraints)?, for example min||Bx - b||^2 -> f(x) = x^t*B^t*B*x - B^t*b*x -> A = B^t * B, a = B^t * b,

Ax=b, which A is spd, can be solved by conjugate gradient method.

2011年6月28日星期二

random number

--------- Possion disk sampling.

--------- Perlin Noise

http://devmag.org.za/2009/05/03/poisson-disk-sampling/

http://devmag.org.za/2009/04/25/perlin-noise/

http://devmag.org.za/2011/06/25/implementing-and-debugging-the-perlin-noise-algorithm/

Bezier curves

http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/

http://devmag.org.za/2011/06/23/bzier-path-algorithms/

近来遇到的问题是怎么求underdetermined systems, 以及minimize a quadratic energy, 我还是好像system of equation 跟 optimization是怎么联系在一起的.

2011年6月25日星期六

Graphics memory size

Sometimes, you may need to how many memory left, we can use the GL_NVX_gpu_memory_info, the code snippet comes from the reference.

#define GL_GPU_MEM_INFO_TOTAL_AVAILABLE_MEM_NVX 0x9048
#define GL_GPU_MEM_INFO_CURRENT_AVAILABLE_MEM_NVX 0x9049
   GLint total_mem_kb = 0;
   glGetIntegerv(GL_GPU_MEM_INFO_TOTAL_AVAILABLE_MEM_NVX, &total_mem_kb);
   GLint cur_avail_mem_kb = 0;
   glGetIntegerv(GL_GPU_MEM_INFO_CURRENT_AVAILABLE_MEM_NVX,&cur_avail_mem_kb);
   fprintf(stderr, "NV totoal mem %ikb, avail mem %ikb, used %ikb.\n", total_mem_kb, cur_avail_mem_kb, (total_mem_kb - cur_avail_mem_kb));

reference:

http://www.geeks3d.com/20100531/programming-tips-how-to-know-the-graphics-memory-size-and-usage-in-opengl/

http://www.tohtml.com/cpp/

http://codeformatter.blogspot.com/2009/06/about-code-formatter.html

2011年4月18日星期一

Better Explained (learn right, not note)

Vector Calculus: Understanding Gradient, Divergence, Flux, Circulation and Curl.

Multivariable calculus and vector analysis (a set of on-line readings), by math.umn.edu/

Discrete Differential Geometry : Theory and Practice. by cs.caltech.edu/

2011年4月7日星期四

Tech Coord

2011年2月1日星期二

阅读笔记

Using hardware acceleration for graphics, on March 13, 2009

Question 1: 给hardware分类.

标准一: 是UnifiedMemoryArchitecture(UMA), 还是Dedicated graphics memoery(Non-UMA) ?

标准二: 根据graphics operations来分five categories.

于是一共十种类型types.

我们在PC上常见的都是Non-UMA + programmable-3D的.

Question 2: How can Qt off-load graphics operations to these different types of hardware?

不同的hardware type有不同的rendering back end(QPaintEngine的具体实现):

Qt \ / QPaintEngine for type X:

| -- QPainter --| QPaintEngine for type Y:

Application / \ QPaintEngine for type Z:

Type UMA Non-UMA

None Raster Raster*

Blitter DirectFB DirectFB**

2D vector OpenVG*** OpenVG***

Fixed-3D OpenGL (ES) 1.x OpenGL (ES) 1.x

Programmable-3D OpenGL (ES) 2.x OpenGL (ES) 2.x****

* When using raster on NUMA, rendering is actually done in system memory first, then flushed to VRAM

** This is the one which is going to be slow when doing anything other than QPainter::drawPixmap()

*** It shouldn’t be a big surprise we’re researching an OpenVG paint engine!

**** Qt 4.5 contains a new paint engine for OpenGL ES 2.x which we’re now making work on desktop OpenGL 2.0.

Qt Graphics and Performance – An Overview, on December 16, 2009

关于QWidget and QWindowSurface:

关于Graphics systems:

You can select graphics systems either by starting the application with the command line option -graphicssystem raster|opengl|opengl1|x11|native, where “native” means to use the system default. Another option is to provide the exact same option to configure which will set that option for all applications using Qt. Finally there is the function QApplication::setGraphicsSystem which hardcodes the graphics system for a given application.

关于Images and Pixmaps:

The difference between these two is mostly covered in the documentation, but I would like to highlight a few things none the less.

Our documentation says: “QImage is designed and optimized for I/O, and for direct pixel access and manipulation, while QPixmap is designed and optimized for showing images on screen.”

这有点像Image跟Texture的区别, 后者可能是前者的封装加上一个OpenGL texture ID以便render.

Qt Graphics and Performance – OpenGL, on January 6, 2010

什么是OpenGL, 为什么选择OpenGL ES 2.0?

QPainter将东西传给OpenGL来画, GL paint engine turn the whole of the QPainter API into "just a bouch of triangles". 举了一个例子说明.

Interleaved Rendering：

void widget::paintEvent(QPaintEvent *)

{

QPainter .... // 不同的painter来画.

QPainter .... //

}

Mixing QPainter and Native OpenGL

QGLWidget vs OpenGL Graphics-System

我看懂了OpenGL paint engine, 但是不懂OpenGL Graphics-System是什么概念, 为什么跟QGLWidget来比较, 后者全部东西都是用OpenGL paint engine来画, "all use the OpenGL paint engine regardless of what graphics system is being used. QGLWidget is basically a regular widget which always has a native window ID and is always rendered to using OpenGL. You are free to choose whichever method you want to get OpenGL rendering (graphics system or QGLWidget). However, using the opengl graphics system can often be slower than using a QGLWidget". 是说我们App中可以选择用QGLWidget或者OpenGL graphics system?

QGLWidget的缺点是不能局部sub-area更新, 需要重画整个widget.

2011年1月23日星期日

有些图案是artist随性的创作，有些是规律的，当中有对称的有pattern的，前者我做不了啦，后者倒是可以学学。
下面是这两天收集的blogs.

------
http://www.subblue.com/blog 上面很多用Pixel Bender做的fractal的效果, 他甚至"The images were rendered using a new fractal renderer I'm working on in Pixel Bender. I'll be releasing it once I'm happy with the final script."
然后好奇地查了一下:

Adobe Pixel Bender Tookit 我理解为是Image Processing工具.
Adobe Pixel Bender is a programming language that is used to create or manipulate image content. Using Pixel Bender you create a kernel, also known in this document as a shader. The shader defines a single function that executes on each of the pixels of an image individually.
In Flash Player and Adobe AIR, three types of effects can be easily created using a shader: drawing fill, blend mode, filter.
Note: Pixel Bender support is available starting in Flash Player 10 and Adobe AIR 1.5.

ActionScript is the programming language for the Adobe Flash Player and Adobe AIR run-time environments. It enables interactivity, data handling, and much more in Flash, Flex, and AIR content and applications.

他多次提到用了这里的技术http://iquilezles.org/www/, http://iquilezles.org/www/articles/mandelbulb/mandelbulb.htm, http://iquilezles.org/www/articles/ssao/ssao.htm, 原来还有http://iquilezles.org/prods/index.htm

还提到一个不错的forum, http://www.fractalforums.com/3d-fractal-generation/true-3d-mandlebrot-type-fractal.
-----------------
另一blog
http://blog.hvidtfeldts.net/index.php/2007/05/
他的作品http://structuresynth.sourceforge.net/ Structure Synth is a cross-platform application for generating 3D structures by specifying a design grammar. Even simple systems may generate surprising and complex structures. The design grammar approach was originally devised by Chris Coyne (for a 2D implementation see the popular Context Free Art).
用语法grammar生成模型结构.
http://www.contextfreeart.org/ Context Free is a program that generates images from written instructions called a grammar. The program follows the instructions in a few seconds to create images that can contain millions of shapes.

Context Free提到了用Anti-Grain Geometry(AGG)来做底层的2D graphics library. 原来AGG是很有名的2D rendering engine http://www.antigrain.com/about/index.html，Qt的2D Raster Engine在实现时候也考虑过AGG(http://labs.qt.nokia.com/2009/12/18/qt-graphics-and-performance-the-raster-engine/). AGG只是software rendering, 没有用到GL-based acceleration.

Cairo is a 2D graphics library with support for multiple output devices (貌似也叫back ends). Currently supported output targets include the X Window System, Quartz, Win32, image buffers, PostScript, PDF, and SVG file output. Experimental backends include OpenGL, XCB, BeOS, OS/2, and DirectFB, 还有Qt等.

Skia is a complete 2D graphic library for drawing Text, Geometries, and Images. 3x3 matrices w/ perspective;antialiasing, transparency, filters;shaders, xfermodes, maskfilters, patheffects.
New backend for GPUs: There is a new library, sitting along side skia. Next to src/ and include/ is gpu/. This stand-along library is an abstraction for drawing 2D primitives to a GPU. GrContext.h is the header you should read first. Skia can use this to redirect 100% of its drawing to the GPU, via subclasses in src/gpu. SkGpuCanvas and SkGpuDevice.
------
http://processing.org/ 貌似是一种很popular的create images, animations, and interactions的open source programming language. 是基于Java的，文档倒是很清晰.
还有几本本评价很高books，其一是:
Processing: A Programming Handbook for Visual Designers and Artists [Hardcover].

------
先学习一些math and formula, 生成一些经典的shape and fractal, 2D的话考虑用AGG/Cairo/Skia/Qt等来render比较方便, 3D的话当然需要用OpenGL来render.

2011年1月21日星期五

the main theme of this stage is bug fixing for me, but still sth can be learned from:

其中左边是一个(0,0) to (1,1)的方形square, 右边是一个(1,0) to (2,1)的方形square, 怎么判断三角形是在其中一个square里面，而不是跨过了两个squares呢，像那个红色的三角形? 运行三角形triangle刚好接触到两边界, 如那个大的green三角形.

下面只看横方向的坐标，纵向的Yaxis也类似：

bool isCrossSquare = (int)start.x != (int)end.x; 错的. 因为int是四舍五入, int(-0.2) = 0. bool isCrossSquare = floor(start.x) != floor(end.x); 对的.

当然还得考虑特殊情况，像上面的大绿色三角形:

floor(start.x) = 0, floor(end.x) = 1, 但end.x == floor(end.x)表示右边压界，所以例外。

还得考虑横跨了两个square并刚好压界.

完整的判断是:

bool isCrossSquare = (floor(start.x) != floor(end.x) && end.x != floor(end.x)) || (end.x - start.x > 1);

其中一个应用实例是判断uv layout有没有超出范围.

2011年1月20日星期四

今天有看到box filter这名词了, ptex的paper中提到用box filter做symmetric reductions of each texture(also use asymmetric reduction for anisotropic filtering), 于是又想回顾一下这些概念.

什么是filter (filter kernel)? hint: a pattern.

什么是convolution? 什么是image filtering?

Box filter这里的box好像是指这个filter的形状shape, 例如3*3, 而像Bicubic filter这filter的shape在一维来看是曲线，二维来看估计是圆形. (可能用box filter来跟bicubic filter来做比较不是十分合适，我的理解中box filter好像是指一类filter，只要它们的shape都是rectangle, 而bicubic filter好像是特地的一种, 但又可能不是，因为bicubic函数系数不一样得到的curve是不一样的？)

Box filter是系数都是positive, 于是起到的是模糊smooth的效果，而Bicubic filter的系数weight中山有negative的，于是能起到a slight sharpening effect.

在GPU中实现时候为了避免bicubic的计算，可以用look-up table的方法(在CPU中建float-precision texture). 具体看[1].

Reference:

[1] High-Quality Filtering http://http.developer.nvidia.com/GPUGems/gpugems_ch24.html

下面是对box filter和bilinear filter的感性区别, box filter是求中间11号texel时候用包括自身在内的9个texel做平均(也可以理解为系数固定的线插interpolation)，而bilinear filter是图片放大or缩小or大小不变但是错位时候求自身texel时候对最近的4个做线插, 线插的系数跟自身texel离那4个texels的距离有关, bilinear filter常见于OpenGL (or GPU hardware) interpolation(texture filtering), 例如在magnification情况下一个texel占了多个pixels, 那每一pixel的color就找最近的4个Texels用bilinear interpolation，这类似于把image缩小，小的image的一个texel相当于在大的image的多个texel的线插.

2011年1月18日星期二

Motorcycle Graphs: Canonical Quad Mesh Partitioning.(摩托车图: 标准的四边形网格剖分:-)
A mesh is structured if it has no extraordinary vertices, and unstructured otherwise. The main subjects of this paper are structured partitions in which the quadrilaterals of a mesh (semi-regular mesh) are partitioned into a small number of structured submeshes.

Extraordinary vertices都是作为分界点, 假如user先选择两个extraordinary vertices然后连在一起，是不是会加快计算呢?

These are examples and resources about renderer:

Ray Tracing:

YafaRay: .

LuxRender: original based on PBRT in 2007.

Physically Based Rendering, Second Edition: From Theory To Implementation by Matt Pharr.

Ray Tracing from the Ground Up by Kevin Suffern.

RenderMan compliant renderers:

Pixar RenderMan(PRman): RiSpec, the RenderMan Interface Specification. It is built around the REYES algorithm. The popular shading language is RSL developed by Pixar. OSL released by Sony is another story(check the OpenImageIO too).

Aqsis: Open source 3D solution adhering to the RenderMan interface standard by Pixar Animation Studios.

Pixie, a bit like a dead project since 2005.

3Delight, 6 months of free license.

From this pic, RenderMan is just an API to communicate with renderers(RenderMan is not a renderer, it is an interface description. But often renderman is used as a synonym for the render PRman itself). There are two main parts of RenderMan: 3D scene description language(.rib, RenderMan Interface Bytestream), and Programable shading language(.sl). Introduction to PRman.