BSP树、四叉树、八叉树与 KD 树

这学期当了《计算机游戏程序设计》这门课的助教,导师要求我给本科生的小朋友们详细讲下四叉树、八叉树、KD 树等游戏场景管理中的数据结构,下面是我做的课件,顺便测试了下 hexo 博客里直接显示 PDF 文件。



WebGL初探

Coursera 上最近新开了一门课 Interactive Computer Graphics with WebGL,通过 WebGL 来介绍计算机图形学。

从本科时学习 OpenGL 1.x ,到研一重新学习 OpenGL 3.x 之后基于 shader 的方法,OpenGL 也算是我的一位老朋友了。现在 Web 开发热火朝天,桌面应用 Web 化早已成为趋势,我正好借着这门课学习下 WebGL,同时也了解一下网络前端开发。


OpenGL

OpenGL = Open Graphics Library,是图形硬件的一种标准软件接口,其最初由 SGI 创建,用于在不同硬件体系结构的图形设备上进行二维和三维图形的绘制。OpenGL 不是一种编程语言,也不是 OpenCV 之类的算法工具库,而是一个图形显示标准 API 集合。


Modern OpenGL

学习过 OpenGL 1.x 和 2.x 的朋友应该对 glBegin()glVertex()glEnd() 印象深刻,使用这种方式绘制属于“立即模式”(immediate mode),每次顶点被创建后都会由 CPU 发送给 GPU 进行绘制,从而造成了 CPU 和 GPU 之间的性能瓶颈。

立即模式在 OpenGL 3.1 及之后的版本已经被移除,Modern OpenGL 是基于 Shader 来进行图形的绘制的,即所有绘制工作都应由 GPU 负责,CPU 仅仅负责将要绘制的数据传送给 GPU。

Shader(着色器) 也是一种程序,其使用 GLSL(GL Shading Language) 编写,分为顶点着色器(vertex shader)和片段着色器(fragment shader),前者处理顶点相关的属性,后者处理像素点相关的属性。着色器在程序运行时进行编译。

Modern OpenGL 通过“保留模式”(retained mode) 进行图形绘制:将所有顶点数据放在一个数组中,将该数组发送给 GPU ,通过 shaders 完成绘制。


WebGL

WebGL 是 OpenGL ES 2.0 的 JavaScript 实现,是面向浏览器的 OpenGL。WebGL 可以与 HTML5、CSS 结合使用,借助本地系统显卡在浏览器中构建和显示三维场景与模型。

WebGL 使用 JavaScript 作为编程语言,尽管有一些问题和局限性,但能在浏览器轻松构建三维图形程序仍是一件很酷的事!


柴郡猫技术--C++中的PIMPL设计模式

C++ 中的“柴郡猫技术”(Cheshire Cat Idiom),又称为 PIMPL(Pointer to IMPLementation) ,Opaque Pointer 等,是一种在类中只定义接口,而将私有数据成员封装在另一个实现类中的惯用法。该方法主要是为了隐藏类的数据以及减轻编译时的压力。

“柴郡猫”是什么鬼?就是下面这货:

Cheshire Cat

使用 OpenCV 裁剪 PDF 页面

网上找到的一些课件讲义等资料有时候会是 PPT 多页打印而成的 PDF 文件,比如下图这种:

slides in pdf

有些人希望对 PDF 页面进行裁剪,将 PDF 还原为原 slides 那样一页一张演示文稿的形式。(其实我个人觉得没什么必要,因为不影响阅读,而且 PDF 格式读起来还不用频繁翻页了。)

前几天,我在知乎上看到了有这样需求的一个问题
当时想到用 Python 和 OpenCV 来做这样的图像处理小任务应该很简单的吧。于是动手撸了段代码,简单的 “边缘检测+轮廓提取”,最后结果看起来还不错:

pdf cropped results

下面给出 Python 代码并简单解释下。

C++ 中的 lambda 表达式

lambda 表达式是函数式编程语言中一个很 cool 的特性,而 C++11 标准加入了对 lambda 表达式的支持。本篇文章对 C++11 中的 lambda 表达式做一个简单的介绍。



什么是 lambda 表达式

说到 lambda expression 就不能不提 lambda calculus,前者是从后者中衍生出的概念,lambda calculus 有着严格的数学定义,与图灵机有着等价的计算能力。这里只介绍编程语言中的 lambda 表达式概念。

在函数式编程语言中,函数是一等公民。有时我们需要一个函数,但又不想要定义一个具有名字的函数,即我们需要一个匿名函数,而一个 lambda 表达式实际上就是通过表达式的方式定义了一个匿名函数。

旋转矩阵与四元数

在计算机图形学的学习中,几何变换(Transformations)是一块重要的内容,我们使用齐次坐标(Homogeneous coordinates)描述点和向量,使用变换矩阵描述平移、旋转等变换。

而在平移、旋转、缩放这几种变换中,又以旋转的情况最为复杂。实际上,计算机图形学中三维空间的旋转不仅仅有旋转矩阵一种表达形式,欧拉角(Euler angles)和四元数(Quaternions)也是常用的方法。

Kinect开发环境配置:Kinect for Windows SDK + OpenCV2.4.9 + VS2013 + Win8(x86)

OS为Windows 8 32位,VS2013已安装并可以正常使用。

一. 安装和配置Kinect for Windows SDK v1.8

官方网站下载Kinect for Windows SDKDeveloper Toolkit

KinectSDK-v1.8-Setup.exe (主要提供Kinect的驱动和设备访问接口)

KinectDeveloperToolkit-v1.8.0-Setup.exe (主要提供一些有助于开发的工具,包括Kinect Studio和多种编程语言的开发例程等)

Ruby Quick Start (4) -- Array, String, Closure

《Ruby语言入门教程v1.0》笔记(4)


第八章 Ruby中的数组、字符串、闭包

1. Ruby中的数组

1.1 建立数组

1
2
3
4
5
6
arr1 = []
arr2 = Array.new
arr3 = ['4 ', '5 ', '6 ']
print arr1, "\n"
print arr2, "\n"
print arr3, "\n"



1.2 访问数组元素

1
2
3
4
5
6
7
8
9
10
arr = [3, 4, 5, 6, 7, 8, 9]
puts arr[0] # 3
puts arr.first # 3
puts arr[arr.length-1] # 9
puts arr[arr.size-1] # 9
puts arr.last # 9
puts arr[-1] # 9
puts arr[-2] # 8
print arr[1..3] ,"\n" # 456
print arr[-3, 2] ,"\n" # 78

数组的索引从 0 开始,一直到数组的长度减去 1

负数表示从数组末尾开始的索引;

用一对数字来索引数组,第一个数字表示开始位置,第二数字表示从开始位置起的元素数目。



1.3 增加、删除数组元素

Ruby 的数组大小是动态的,你能够随时增加、删除数组元素。

Ruby Quick Start (3) -- Module, Mix-in

《Ruby语言入门教程v1.0》笔记(3)



第六章 模块、命名空间、Mix-in

1. Ruby中的模块

在程序中,相关的、不相关的代码的组合,叫作模块。一般情况下,我们总是把功能相关的代码放在一个模块里。

把功能相关的程序代码放在一个模块里, 体现了模块的第一个作用: 可以被其它程序代码重复使用。

数学中常用的函数, Ruby 中的 Math 模块都提供了。 每个使用 Math 模块的程序员无须再重复编写这些常用的函数与常数。

1
2
puts Math.sqrt(2) # 1.4142135623731
puts Math::PI # 3.14159265358979

定义模块用 module...end

模块与类非常相似,但是:

  • 模块不可以有实例对象;
  • 模块不可以有子类。

Notes of Scala course on Coursera -- Week 3

Here are my notes for the week 3’s lecture of Functional Programming Principles in Scala on Coursera.





1. Class Hierarchies

1.1 Abstract Classes

Consider the task of writing a class for sets of integers with the following operations.

1
2
3
4
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}

IntSet is an abstract class.

Abstract classes can contain members which are missing an implementation (in our case, incl and contains ).

Consequently, no instances of an abstract class can be created with the operator new.



1.2 Class Extensions

Let’s consider implementing sets as binary trees.

There are two types of possible trees: a tree for the empty set, and a tree consisting of an integer and two sub-trees.

Here are their implementations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
}
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) new NonEmpty(elem, left incl x, right)
else if (x > elem) new NonEmpty(elem, left, right incl x)
else this
}

Empty and NonEmpty both extend the class IntSet .

This implies that the types Empty and NonEmpty conform to the type IntSet

  • an object of type Empty or NonEmpty can be used wherever an object of type IntSet is required.



F**k me on GitHub