分类目录归档:Programming

C++调试经验小结

工作稍微有一段时间了,实践过程中遇到了一些debug方面的问题。涉及到的细节时间长了难免会有遗忘,因此在这里记录下来,也希望能对其他正在和bug做苦苦斗争的同学能有所帮助。

  • valgrind
    这工具是Linux下面检查内存错误的大杀器,主要用来程序在内存操作上的问题,包括越界读写,内存泄露等。具体工作原理可以参考这里
    valgrind最大的问题是,它是在运行时检查程序的内存问题的,会让程序的运行速度降低20倍左右。对于玩具程序而言这不是什么问题,但是如果你的程序初始化就需要十分钟的话,用它来检查问题的可操作性就很弱了。
    另外一个问题是,valgrind不能设置检查的范围(也可能是我不会使)。如果你的程序需要链接各种外部库,那么很可能你需要检查的错误信息会淹没在外部库的出错信息里面。
  • gdb调试
    用gdb调试程序应该是每一个linux下c++程序员的必修课,不过对于内存越界仍然有一些trick可以用。
    对于最理想的越界情况,类的成员变量或者堆上的数据被破坏导致程序出错,这时候只需要定位到出错时候出问题的数据内存地址,再用watch *0×12345这样的方式设置watch断点,就可以断到导致越界的凶手处了。
    不过内存越界往往会破坏一些奇怪的地方,导致gdb看上起根本没法儿调试。比如有时候越界写可能导致c++对象的虚函数表被破坏,这种情况会导致出错时候最后一层函数的调用堆栈变成问号。因为虚函数表其实就是保存在对象开头处的内存指针,只需要针对出错对象的内存地址使用watch断点就可以找到犯罪现场了。
  • 静态代码检查
    相比较于valgrind, gdb这些费时费力亡羊补牢的方式,静态代码检查工具可能会省掉很多不必要的调试时间。最常用的可能就是cppcheck这个工具了,它会检查数组越界、内存泄露、资源未释放等等问题。
  • 性能调优
    可能很多人会使用log日志等方式来自己统计性能。但是这么做统计的粒度取决于日志输出的频率,同时还需要使用宏或者其他方式针对release和debug环境做不同的处理。目前看来最好用的方案是google的性能统计工具gperf tools。这个工具的优点在于可以进行函数级别的性能统计,对程序本身的性能影响可控(取决于你需要的统计频率,用户可以针对统计精度和性能影响之间做权衡),并且可以不用修改程序源代码。
    gperf tools的使用本身没有什么好说的,需要注意的一点是,使用官方推荐的libunwind(一个gperf tools的依赖库)版本会导致程序崩溃,我在使用最新的git上的版本以后没有遇到问题。
    对于需要统计性能的程序,需要在编译时候使用-g参数将函数符号编译进去,否则最终统计出来的性能数据中只能看到内存地址,看不到函数名。
    最后一个需要注意的地方就是,如果被统计的程序一直处于挂起状态是没法儿统计到数据的。gperf tools需要程序一直占用cpu,然后才会进行断点统计。
VirusBuster_title_small

VirusBuster — Shanghai Gamejam 2013参赛作品

上周末(7月19)被石曦拽去上海参加了第三届Shanghai Gamejam,然后还拉上了鹏鹏。到了现场发现全是码农的天下,美术总数不超过10个人。比赛现场拉了几个人,最后组成了一个6个人的小团队,通过两天的奋战做出来了这款Virus Buster。

VirusBuster_title_small

比赛的主题是“异类”,讨论后决定做这个白细胞吞噬其他病毒的休闲类游戏。引擎使用了Unity,发现用Unity做2D游戏开发效率非常高。结合引擎内置的Physix,直接省掉了碰撞检测、物理控制等工作。另一方面,因为用的语言是C#,进一步降低了代码量。

一开始的版本是完全没有挑战的类似吃豆子感觉的东东,大家觉得太没有挑战,于是加入了障碍物、会发射子弹的敌人等等东东。觉得难度还不够,于是又增加了玩家控制的惯性,同时还加入了每吃一个病毒会加速的设计。结果到后来感觉做的这个游戏越来越像“是男人就撑30秒”了。美术这边小强为各位病毒同学加上了小脸,于是整个游戏有了一种莫名的萌感。带刺的荆棘(或者说是树枝?)会随着游戏进程不断长出来,然后还会随着水流诡异摇来摇去,等着玩家撞上去送死 囧。

到比赛结束提交最终版本的时候游戏已经有了初步的可玩性。不过因为始终只是两天搞出来的东西,游戏内容并不是很长。期待后续加入更复杂的关卡和敌人后会更加吸引人;除此之外放到iOS和android上面用陀螺仪来控制也应该会很有趣。感兴趣的童鞋到下面去下载比赛时提交的版本来试试吧。

 

点这里下载

 

 

基于OpenCV的简单图片特征匹配

前两个月闲的蛋疼做了一个图片匹配的东东,原本以为直接用OpenCV就可以用图像特征的方式来做了,结果发现OpenCV只是封装了比较低层的特征识别算法,并没有高级的端口。这里把特征匹配的实现思路记录如下:

1. 计算出descriptor:

1
2
3
4
5
Mat img = imread(filename);
cv::Feature2D *detector = new cv::OrbFeatureDetector();
cv::Feature2D *extractor = new cv::OrbDescriptorExtractor();
detector->detect(img, kpImg);
extractor->compute(img, kpImg, descImg);

其中的detector负责提取图片中的特征点,并由extractor提取出descriptor,最终保存到descImg中。

2. 两张图片的descriptor进行对比

1
2
3
4
5
6
7
8
BruteForceMatcher< L2 > matcher;
matcher.knnMatch(desc1, desc2, matches1, 2);
matcher.knnMatch(desc2, desc1, matches2, 2);
 
ratioTest(matches1);
ratioTest(matches2);
 
symmetryTest(matches1, matches2, symMatches);

首先会使用BruteForceMatcher找出两个descriptor到对方的配对点,然后使用ratioTest和SymmetryTest来剔除不靠谱的匹配特征点,也就是下面所要说的剔除匹配点的操作。

3. 剔除低质量匹配点
ratioTest用来剔除距离比例相差过大的配对点,配对点之间的距离相差越大,能匹配上的概率也就越小。这里使用一个参数ratio来控制剔除距离相差在一定范围之外的特征点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int ratioTest( VVecMatch &matches )
{
  float ratio = 0.8f;
  int removed=0;
  // for all matches
  for (std::vector<std::vector>::iterator
    matchIterator= matches.begin();
    matchIterator!= matches.end(); ++matchIterator) 
  {
    // if 2 NN has been identified
    if (matchIterator->size() > 1) 
    {
      // check distance ratio
      if ((*matchIterator)[0].distance/
        (*matchIterator)[1].distance > ratio) {
          matchIterator->clear(); // remove match
          removed++;
      }
    } else { // does not have 2 neighbours
      matchIterator->clear(); // remove match
      removed++;
    }
  }
  return removed;
}

symmetryTest用来判断两个图像间的特征点匹配是否是一一映射,对于不是的点则剔除掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void symmetryTest( const VVecMatch matches1, 
                               const VVecMatch matches2, 
                               VecMatch& symMatches )
{
  // for all matches image 1 -> image 2
  for (std::vector<std::vector>::const_iterator matchIterator1= matches1.begin();
    matchIterator1!= matches1.end(); ++matchIterator1) 
  {
    // ignore deleted matches
    if (matchIterator1->size() < 2)       
      continue;
 
    // for all matches image 2 -> image 1
    for (std::vector<std::vector>::const_iterator matchIterator2= matches2.begin();
      matchIterator2!= matches2.end();
      ++matchIterator2) 
    {
      // ignore deleted matches
      if (matchIterator2->size() < 2)         
        continue;       
      // Match symmetry test
      if ((*matchIterator1)[0].queryIdx ==
         (*matchIterator2)[0].trainIdx &&
         (*matchIterator2)[0].queryIdx ==
         (*matchIterator1)[0].trainIdx)
        {
         // add symmetrical match
         symMatches.push_back(
           cv::DMatch((*matchIterator1)[0].queryIdx,
           (*matchIterator1)[0].trainIdx,
           (*matchIterator1)[0].distance));
         break; // next match in image 1 -> image 2
      }
    }
  }
}

4. 判断是否匹配上

经过上面的特征匹配和剔除,剩下来的应该都是比较靠谱的匹配点了。如果用一个图片来和一个模板集合来进行比对,那么通过简单的比较能够匹配到的特征点数目就能够判断出是否匹配上了。

PS:对于OpenCV中的所有特征匹配算法都可以用这个办法来做,比如SIFT, SURF等等。只需要简单的替换第一步中的extractor和detector就可以了

跨平台CMake预编译头文件脚本(更新)

在之前的一篇blog里面我放出了一个能够同时在Visual Studio和GCC下面使用的预编译头文件的CMake生成脚本。放到项目中实际使用了以后发现了一些问题,经过修改以后的脚本修正了一些bug,同时把生成和使用预编译头的逻辑分离开。这意味着可以在一个项目中生成一个预编译头,然后在其它项目中重用它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
# 创建预编译头
# Target是用来生成预编译头的项目Target;PrecompiledHeader和PrecompiledSource分别是头文件的路径
MACRO(ADD_PRECOMPILED_HEADER
    Target PrecompiledHeader PrecompiledSource)
 
  IF(MSVC)
    ADD_MSVC_PRECOMPILED_HEADER(${PrecompiledHeader}
      ${PrecompiledSource})
  ENDIF(MSVC)
 
  IF(CMAKE_COMPILER_IS_GNUCXX)
    ADD_GCC_PRECOMPILED_HEADER(${Target} ${PrecompiledHeader})
  ENDIF(CMAKE_COMPILER_IS_GNUCXX)
ENDMACRO(ADD_PRECOMPILED_HEADER)
 
# 在生成一个预编译头以后就可以调用这个宏来指定源文件来使用它
# SourcesVar是一个包含了要使用该预编译头的源文件列表
MACRO(USE_PRECOMPILED_HEADER SourcesVar)
  IF(MSVC)
    USE_MSVC_PRECOMPILED_HEADER(${SourcesVar})
  ENDIF(MSVC)
 
  IF(CMAKE_COMPILER_IS_GNUCXX)
    USE_GCC_PRECOMPILED_HEADER(${SourcesVar})
  ENDIF()
ENDMACRO(USE_PRECOMPILED_HEADER)
 
# 用于为visual studio生成pch
MACRO(ADD_MSVC_PRECOMPILED_HEADER PrecompiledHeader PrecompiledSource)
  GET_FILENAME_COMPONENT(PrecompiledBasename
    ${PrecompiledHeader} NAME_WE)
 
  # 得到pch文件的文件名
  SET(PrecompiledBinary
    "${CMAKE_CURRENT_BINARY_DIR}/${PrecompiledBasename}.pch")
 
  SET(PCH_BIN_PATH
    ${CMAKE_CURRENT_BINARY_DIR}/${PrecompiledBasename}.pch
    CACHE INTERNAL "the path of the precompiled binary")
  SET(PCH_PATH
    ${CMAKE_CURRENT_SOURCE_DIR}/${PrecompiledHeader}
    CACHE INTERNAL "the path of the precompiled header")
 
  # 为visual studio设置用于生成pch的编译器参数
  SET_SOURCE_FILES_PROPERTIES(
    ${PrecompiledSource}
    PROPERTIES COMPILE_FLAGS
    "/Yc\"${PrecompiledHeader}\" /Fp\"${PrecompiledBinary}\""
    OBJECT_OUTPUTS "${PrecompiledBinary}")
ENDMACRO(ADD_MSVC_PRECOMPILED_HEADER)
 
MACRO(USE_MSVC_PRECOMPILED_HEADER SourcesVar)
  SET(Sources ${${SourcesVar}})
 
  message("using pch: ${PCH_BIN_PATH} for ${${SourcesVar}}")
 
  set(PrecompiledBinary ${PCH_BIN_PATH})
 
  # 对需要使用pch的源文件设置编译器参数
  SET_SOURCE_FILES_PROPERTIES(${Sources}
    PROPERTIES COMPILE_FLAGS
    "/Yu\"${PrecompiledBinary}\" /FI\"${PrecompiledBinary}\" /Fp\"${PrecompiledBinary}\""
    OBJECT_DEPENDS "${PrecompiledBinary}")
ENDMACRO(USE_MSVC_PRECOMPILED_HEADER)
 
# 改函数用于判断gcc是否支持预编译头
IF(CMAKE_COMPILER_IS_GNUCXX)
  EXEC_PROGRAM(
    ${CMAKE_CXX_COMPILER}
    ARGS                    --version
    OUTPUT_VARIABLE _compiler_output)
  STRING(REGEX REPLACE ".* ([0-9]\\.[0-9]\\.[0-9]) .*" "\\1"
    gcc_compiler_version ${_compiler_output})
  #MESSAGE("GCC Version: ${gcc_compiler_version}")
  IF(gcc_compiler_version MATCHES "4\\.[0-9]\\.[0-9]")
    SET(PCHSupport_FOUND TRUE)
  ELSE(gcc_compiler_version MATCHES "4\\.[0-9]\\.[0-9]")
    IF(gcc_compiler_version MATCHES "3\\.4\\.[0-9]")
      SET(PCHSupport_FOUND TRUE)
    ENDIF(gcc_compiler_version MATCHES "3\\.4\\.[0-9]")
  ENDIF(gcc_compiler_version MATCHES "4\\.[0-9]\\.[0-9]")
ENDIF(CMAKE_COMPILER_IS_GNUCXX)
 
MACRO(USE_GCC_PRECOMPILED_HEADER SourcesVar)
  SET(Sources ${${SourcesVar}})
 
  # 通过-include参数让所有源文件强制包含预编译头
  FOREACH(source ${_sourcesVar})
    SET_SOURCE_FILES_PROPERTIES(${source}
      PROPERTIES
      COMPILE_FLAGS "-include ${_name} -Winvalid-pch"
      OBJECT_DEPENDS "${PCH_PATH}")
  ENDFOREACH(source)
ENDMACRO(USE_GCC_PRECOMPILED_HEADER)
 
MACRO(ADD_GCC_PRECOMPILED_HEADER TargetName PrecompileHeader)
  SET(_compile_FLAGS ${CMAKE_CXX_FLAGS})
 
  SET(_input "${CMAKE_CURRENT_SOURCE_DIR}/${PrecompileHeader}")
  MESSAGE("creating pch: ${_input}")
  GET_FILENAME_COMPONENT(_name ${_input} NAME)
  GET_FILENAME_COMPONENT(_path ${_input} PATH)
 
  # 根据不同的编译配置生成预编译头二进制文件的文件名,比如debug.c++, release.c++
  SET(_outdir "${CMAKE_CURRENT_BINARY_DIR}/${_name}.gch")
  IF(CMAKE_BUILD_TYPE)
    SET(_output "${_outdir}/${CMAKE_BUILD_TYPE}.c++")
    LIST(APPEND _compile_FLAGS ${CMAKE_CXX_FLAGS_${CMAKE_BUILD_TYPE}})
  ELSE(CMAKE_BUILD_TYPE)
    SET(_output "${_outdir}/default.c++")
  ENDIF(CMAKE_BUILD_TYPE)
 
  IF(${CMAKE_BUILD_TYPE} STREQUAL "DEBUG")
    LIST(APPEND _compile_FLAGS "-DQT_DEBUG")
  ENDIF()
 
  # 自动创建文件夹
  ADD_CUSTOM_COMMAND(
    OUTPUT ${_outdir}
    COMMAND mkdir ${_outdir} # TODO: {CMAKE_COMMAND} -E ...
    )
 
  GET_DIRECTORY_PROPERTY(_directory_flags INCLUDE_DIRECTORIES)
 
  # 确保生成预编译头的文件夹在所有包含目录的最前面
  SET(_CMAKE_CURRENT_BINARY_DIR_included_before_path FALSE)
  FOREACH(item ${_directory_flags})
    IF(${item}  STREQUAL ${_path} AND NOT
        _CMAKE_CURRENT_BINARY_DIR_included_before_path )
      MESSAGE(FATAL_ERROR
        "This is the ADD_PRECOMPILED_HEADER macro. "
        "CMAKE_CURREN_BINARY_DIR has to mentioned at INCLUDE_DIRECTORIES's argument list before ${_path}, where ${_name} is located"
        )
    ENDIF(${item}  STREQUAL ${_path} AND NOT
      _CMAKE_CURRENT_BINARY_DIR_included_before_path )
 
    IF(${item}  STREQUAL ${CMAKE_CURRENT_BINARY_DIR})
      SET(_CMAKE_CURRENT_BINARY_DIR_included_before_path TRUE)
    ENDIF(${item}  STREQUAL ${CMAKE_CURRENT_BINARY_DIR})
 
    LIST(APPEND _compile_FLAGS "-I${item}")
  ENDFOREACH(item)
 
  GET_DIRECTORY_PROPERTY(_directory_flags DEFINITIONS)
  #LIST(APPEND _compile_FLAGS "-fPIC")
  LIST(APPEND _compile_FLAGS ${_directory_flags})
 
  SEPARATE_ARGUMENTS(_compile_FLAGS)
  #MESSAGE("_compiler_FLAGS: ${_compile_FLAGS}")
 
  # 拷贝头文件到binary目录
  ADD_CUSTOM_COMMAND(
    OUTPUT  ${CMAKE_CURRENT_BINARY_DIR}/${_name}
    COMMAND ${CMAKE_COMMAND} -E copy  ${_input}
    ${CMAKE_CURRENT_BINARY_DIR}/${_name}
    )
 
  SET(PCH_PATH ${CMAKE_CURRENT_BINARY_DIR}/${_name} CACHE INTERNAL
    "the path of the precompiled header")
 
  #MESSAGE("command : ${CMAKE_COMMAND} -E copy  ${_input}
  #  ${CMAKE_CURRENT_BINARY_DIR}/${_name}")
 
  # 添加用于生成预编译头的命令
  ADD_CUSTOM_COMMAND(
    OUTPUT ${_output}
    COMMAND ${CMAKE_CXX_COMPILER}
    ${_compile_FLAGS}
    -x c++-header
    -o ${_output}
    ${_input}
    DEPENDS ${_input} ${_outdir} ${CMAKE_CURRENT_BINARY_DIR}/${_name}
    )
  ADD_CUSTOM_TARGET(${TargetName}_gch
    DEPENDS ${_output}
    )
  ADD_DEPENDENCIES(${TargetName} ${TargetName}_gch )
ENDMACRO(ADD_GCC_PRECOMPILED_HEADER)

对于Visual Studio而言情况比较简单,只需要分别对预编译头和使用预编译头的文件设置一下参数就可以了。GCC的设置就比较蛋疼了,GCC规定预编译头的头文件和生成的二进制文件必须在同一个目录下。因为CMake在编译时一般编译文件夹和源代码文件夹是分开的,所以这里把用于生成pch的头文件拷贝到编译文件夹中。除此之外,还需要手动配置源文件和预编译头之间的依赖关系。

具体使用的使用时会像下面这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
PROJECT(TEST_PROJECT)
 
# 这里设置好各种编译设置,并且假定所有源文件保存在Sources这个变量里面
 
# 像平常一样添加一个executable或者library
ADD_EXECUTABLE(TestProject ${Sources}) 
 
# 头文件的文件名可以任意,并且gcc下面其实并不需要StdAfx.cpp,但是考虑到对Visual Studio的兼容性,
# 这里仍然需要一个cpp文件
ADD_PRECOMPILED_HEADER(TestProject StdAfx.h StdAfx.cpp) 
 
# 然后简单的一个调用就搞定了
USE_PRECOMPILED_HEADER(Sources)

如果在另外一个Project中需要使用之前生成的预编译头,只需要在执行完ADD_PRECOMPILED_HEADER以后直接在那个project中调用USE_PRECOMPILED_HEADER就可以了。

处理Emacs中的行号和空白字符

做过开源项目的童鞋可能会知道,在很多开源项目中会有专门的脚本来检查代码风格。其中包括行尾是否有多余的空白字符,是否使用使用tab,每一行是否超过了指定的宽度等等。这些问题通常在敲代码的时候并不容易看出来,等到要提交代码的时候才发现问题。稍微搜索了一下发现在emacs中有一个很有用的whitespace插件可以解决这个问题。

whitespace可以针对设置的规则对上面提到的问题进行高亮显示,效果如下:

WhiteSpaceOnLight

whitespace具体可以找到的问题包括tab, 空格混用;行尾多余的空白字符;文件结束前的空白字符;超过指定长度的行等等。可以通过设置whitespace-style来指定需要提示哪些问题。在我的配置中使用了如下配置:

1
2
3
4
5
6
7
;; deal with white spaces
(require 'whitespace)
(global-whitespace-mode)
(setq whitespace-style
      '(face trailing tabs lines lines-tail empty
        space-after-tab space-before-tab))
(add-hook 'before-save-hook 'delete-trailing-whitespace)

默认的whitespace-style把整个buffer被搞得有点乱糟糟的,因此我把不是很需要的部分都去掉了,只剩下检测行尾空白、tab等少数几个问题。对于行尾的多余字符而言,一个个删除也是很麻烦的事情。所以我直接用delete-trailing-whitespace在保存的时候把它们都干掉了。

不过在这里whitespace会和行号有一点点冲突。通常为了显示行号都会打开linum-mode,行号会是右边对其的数字。whitespace会认为行号前面的空白字符是问题字符而高亮显示,搞得非常难看。为了解决这个问题可以用下面代码对linum进行设置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
;; Show line number
(require 'linum)
(global-linum-mode t)
(setq column-number-mode t)
(setq line-number-node t)
(setq linum-format "%5d ")
(add-hook 'linum-before-numbering-hook
          (lambda ()
            (let ((w (+
                      (length
                       (number-to-string
                        (count-lines (point-min) (point-max))
                        ))
                      2)
                     ))
              (setq linum-format
                    `(lambda (line)
                       (propertize (concat
                                    (truncate-string-to-width
                                     "" (- ,w (length (number-to-string line)))
                                     nil ?x2007)
                                    (number-to-string line))
                                   'face 'linum))))))

这是从emacs wiki上面抄过来的一段代码,用了一个特殊的unicode字符x2007来设置行号的格式,既能达到右端对其的效果又不会被whitespace误杀。

Emacs中处理日志文件

最近写的东西会将信息输出到一个日志文件中去,每次调试的时候log文件内容都会刷新。每次都手动revert-buffer比较烦人,查了一下发现有一个auto-revert-mode可以自动刷新。下面的配置可以实现对于.log文件调用auto-revert-mode:

1
2
3
4
5
6
7
8
9
10
11
;; auto revert log files
(add-hook 'find-file-hook
          (lambda ()
            (if (string-equal
                 ".log"
                 (substring (buffer-file-name)
                            (search "." (buffer-file-name))))
                (progn
                  (setq auto-revert-mode t)
                  (message "Enabling auto-revert-mode for log file")))
            ))

如果是比较长的日志文件,并且日志使用追加内容的方式添加上去的话,可以将上面的(setq auto-revert-mode t)换成(setq auto-revert-tail-mode t)以提高效率。

STL中的红黑树

平时用STL通常只是顺手把vector, map之类常用的类拿来用用就完了,也没有想到去仔细研究里面都有些什么东西。这两天有一个算法程序需要将一堆对象排序,并且会非常频繁的插入删除,对效率的要求极高。原本想用priority queue,但是发现它是对一个数组进行堆排序的方式来操作,效率并不高。在STL的文档里面找了找发现居然没有红黑树,google了一下才知道set, map底层都是用红黑树实现的,只是这个红黑树没有暴露出来给人用。

也不知道是出于什么考虑,性能优秀的红黑树虽然标准库里面有,但是却遮遮掩掩不直接提供给大家用。值得注意的是,因为红黑树是内部使用的类,各个STL实现中的红黑树还不一样。

在VC的实现中红黑树是在xtree文件中的_Tree类,用法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include 
#include 
#include 
 
using namespace std;
 
typedef _Tree< _Tset_traits, allocator, false > > rb_tree;
 
int main()
{
    rb_tree* tree = new rb_tree( less(), allocator() );
    for(int i=35; iinsert(i);
 
    printf("output: %d ", *tree->begin() );
}

gcc中的实现则是在bits/stl_tree.h文件中,而且类的名字和用法都不一样:

1
2
3
4
5
6
7
8
9
10
11
12
#include 
 
typedef _Rb_tree,
                 less > rb_tree;
typedef rb_tree::iterator rb_tree_iter;
 
int main()
{
    rb_tree queue;
    queue._M_insert_unique( int );
    printf("size: %d", queue.size() );
}

尝试给开源项目打补丁

最近开始尝试给开源项目打补丁。首先是跑到Gnome Love上面去逛了一圈。GnomeLove是Gnome官方为了降低开源开发者加入的门槛而搞的一个页面,上面有一些帮助入门的文档链接,从GTK开发到git的使用都有。然后再到Bugzilla上面用GnomeLove作为关键词,能够搜索出一堆比较容易改的bug。
我抓了Empathy的一个bug开始改。Empathy有一个问题就是,它的聊天窗口不会记忆联系人边栏的位置,每次打开一个窗口都需要自己重新拖动它。修改这个bug也很简单,在聊天窗口创建的时候加入一个事件响应函数。然后再在窗口边栏位置变化的时候把这个位置保存在GConf里面,下次窗口打开的时候再把这个数读出来就好了。上次Jesse给Gnome给数独游戏修改bug的时候对方一个多月以后才有反应,不知道这个bug多久以后会有人理我?

3ds Max中导出Cal3D骨骼动画

最近要做一个3d引擎的动画性能测试,所以得为各个引擎导出骨骼动画,其中就包括使用了Cal3D的Crystal Space和OSG。其中Crystal Space本身就可以直接读取Cal3D的骨骼动画,而OSG则是得是用一个名为OsgCal的插件才可以。此外在网上还看到有人在Ogre中使用Cal3D来渲染骨骼动画。

虽然Cal3D用的也算是挺多的,但是很奇怪的是这个项目已经有两三年没有更新了。同时官方文档的描述也很简单,唯一一个官方的教程居然绝大部分篇幅是将如何在3ds max中制作骨骼动画,关键部分如何使用Cal3D插件只有简单的两段话。对于第一次使用Cal3D的人来说肯定会被它搞得一头雾水,而且各个步骤中有一个地方错了都会导致最终的骨骼动画不正确。这里把我试验正确的d导出步骤贴出来:

  1. 导出骨骼
    a. 选择骨骼根节点bip01
    b. 打开Figure Mode
    c. File->Export Cal3D Skeleton
    d. 选择所有骨骼,通常默认即可
  2. 导出材质
    a. 所有纹理必须使用tga格式
    b. 选择骨骼根节点bip01
    c. 打开Figure Mode
    d. 打开材质球,将所有材质命名为material[0], material[1]这样的名称
    e. File->Export->Cal3d Materials
    f. 选择导出的材质(每一种材质分别需要导出一次)
  3. 导出模型
    a. 打开Figure Mode
    b. 选择需要被导出的模型
    c. File->Export Cal3d Mesh
  4. 导出动作
    a. 关闭Figure Mode
    b. File->Export Cal3D Animation
    c. 选择之前导出的谷歌文件
    d. 选择骨骼,默认即可
    e. 选择导出动作的起始结束帧号,帧速和displacement(不知道有什么用?)
  5. 创建xxx.cfg文件,格式如下:

scale=0.1

skeleton=skeleton.csf

animation=running.caf

material=material.crf

注意事项:

  1. Cal3D的导出插件只能支持3ds max 8。如果你是用的9或者更高版本,虽然你已经看了不少内容但是你也只能放弃了:(
  2. 导出时必须严格按照上面所说的顺序依次导出骨骼、材质、模型和动作
  3. 最后创建的.cfg文件中等号左右不要留空格,否则在某些解析程序中(比如说OsgCal中)会导致错误。这应该算是OsgCal的一个小bug。另外OsgCal要求配置文件中scale, skeleton等的顺序不能变,否则也会出错。

RockyRay第一个Demo即将完成

之前由于准备考研复试、毕业答辩和吃散伙饭忙活了好一阵子,现在总算是有点喘息的时间来做点其他事情了。这第一件事情就是继续RockyRay的开发。貌似我以前还没有在blog中提到过RockyRay。

所谓RockyRay是我和小强精力过剩蛋疼无聊的时候满怀着拯救世界解放他人并把爱与和平带给全人类的信念做的一个RPG游戏。恩恩,这也是小强的毕设。因为明天就是小强答辩的日子,结果他在deadline到之前终于完成了第一个场景模型、男主角的模型,以及一些设定图和其他一些CG。第一个游戏场景的Demo已经编译出来,不过还没有打包。明天我就会把整个Demo打包提供下载。整个程序使用Ogre+OgreMax+OpenAL+LuaPlus+Boost,从三月份开始弄到现在(其实中间有将近2个月没有更新)。


感兴趣的童鞋可以先在下面的网址看看小强为RockyRay做的一些2D作品:

http://code.google.com/p/rockyray/



探险
看!灰机!
主角们
排排站,吃果果