C++博客-岁月流转，往昔空明

SoftArt Shader Language Syntax EBNF

空明流转 — Thu, 24 Jul 2008 18:25:00 GMT

经过一晚上的整理，把 SoftArt Shader Language 的 EBNF 弄出来了。
主要参照的是 ISO C++的EBNF 。
由于ISO C++并不是一个LALR(1)能够解决的问题，因此不知道这个C++ EBNF的简化版能否在YACC上比较方便的实现。
如果不能实现，我会先考虑修正语法满足需要，而不是手写编译器，我还没那个能耐。

Flex 与 Bison 的下载地址

//SASL: SoftArt Shader Language

Syntax

Program             ::= DeclSeq

//////////////////////////////////
//Declaration
//////////////////////////////////
DeclSeq             ::= Decl | 
                        DeclSeq Decl
                        
Decl                ::= BlockDecl |
                        FunctioDef

Declarator          ::= DirectDecl [SemanticSpec] [RegisterSpec]

DirectDecl          ::= DeclId |
                        DirectDecl '(' ParamDeclClause ')'|
                        DirectDecl '[' [ConstExp] ']'|
                        '(' Declarator ')'

CvQualifierSeq      ::= CvQualifier [CvQualifierSeq]

CvQualifier         ::= 'const' | 'uniform'

SemanticSpec        ::= ':' Semantic

RegisterSpec        ::= ':' 'register' '(' Register ')'
                        
BlockDecl           ::= SimpleDecl

SimpleDecl          ::= [DeclSpecSeq] [InitDeclList] ';'

AbsDecl             ::= DirectAbsDecl

DirectAbsDecl       ::= [DirectAbsDecl] '(' ParamDeclClause ')' |
                        [DirectAbsDecl] '[' [ConstExp] ']' |
                        '(' AbsDecl ')'
                        

DeclSpecSeq         ::= [DeclSpecSeq] DeclSpec

InitDeclList        ::= InitDecl |
                        InitDeclList ',' InitDecl

InitDecl            ::=    Declarator [Init]

Init                ::= '=' InitClause                         |
                        ( ExpList)
                        
InitClause          ::= AssignmentExp |
                        '{' InitList [','] '}' |
                        '{' '}'
InitList            ::= InitClause |
                        InitList ',' InitClause
                        
DeclSpec            ::= TypeSpec
                        
TypeSpec            ::= SimpleTypeSpec |
                        ClassSpec

SimpleTypeSpec      ::=    'int' | 'half' | 'float' |
                        'int2' | 'half2' | 'float2' |
                        'int3' | 'half3' | 'float3' |
                        'int4' | 'half4' | 'float4' |
                        'float4x4'

/////////////////////////////
//Function
/////////////////////////////
FunctionDef         ::= [DeclSpecSeq] Declarator FunctionBody

FunctionBody        ::= CompoundStatement

/////////////////////////////
//Statements
/////////////////////////////
CompoundStatement   ::= '{' [StatementSeq] '}'

StatementSeq        ::= Statement |
                        StatementSeq Statement

Statement           ::= ExpStatement |
                        CompountStatement |
                        SelectionStatement |
                        IterationStatement |
                        DeclStatement
                        
ExpStatement        ::= [ Expression ] ';'

SelectionStatement  ::= 'if' '(' Condition ')' Statement |
                        'if' '(' Condition ')' Statement 'else' Statement

IterationStatement  ::= 'while' '(' Condition ')' Statement |
                        'do' Statement 'while' '(' Expression ')' ';'
                        'for' '(' ForInitStatement [Condition] ';' [ Expression ] ')' Statement
        
Condition           ::= Expression |
                        TypeSpecSeq Declarator '=' AssignmentExp

ForInitStatement    ::= ExpStatement |
                        SimpleDecl

DeclStatement       ::= BlockDecl

/////////////////////////////                        
//Parameter
/////////////////////////////
ParamDeclClause     ::= [ ParamDeclList ]

ParamDeclList       ::= ParamDecl |
                        ParamDeclList ',' ParamDecl

ParamDecl           ::= DeclSpecSeq Delarator |
                        DeclSpecSeq [AbsDecl]


/////////////////////////////
//Class And Struct
/////////////////////////////
ClassSpec           ::= ClassHead '{' [ MemberSpec ] '}'

ClassHead           ::= 'struct' [ Identifier ]

MemberSpec    `     ::= MemberDecl [MemberSpec]

MemberDeclaration   ::= [DeclSpecSeq] [MemberDeclList]

MemberDeclList      ::= MemberDecl |
                        MemberDeclList ',' MemberDeclarator
                        
MemberDeclarator    ::=    Declarator [ PureSpec ] |
                        Declarator [ ConstInit ] |
                        [ Identifier ] ':' ConstExp



//////////////////////////////////////
//Expressions
//////////////////////////////////////
Expression          ::= AssignmentExp

ConstExp            ::= CondExp

AssignmentExp       ::= CondExp |
                        LogicalOrExp AssignmentOp AssignmentExp
                        
CondExp             ::= LogicalOrExp |
                        LogicalOrExp '?' Expression ':' AssignmentExp

LogicalOrExp        ::= LogicalAndExp |
                        LogicalOrExp '||' LogicalAndExp
                        
LogicalAndExp       ::= InclusiveOrExp |
                        LogicalAndExp '&&' InclusiveOrExp
                        
InclusiveOrExp      ::= ExclusiveOrExp |
                        InclusiveOrExp '|' ExclusiveOrExp
                        
ExclusiveOrExp      ::= AndExp |
                        ExclusiveOrExp '^' AndExp

AndExp              ::= EqualExp |
                        AndExp '&' EqualExp

EqualExp            ::= RelExp |
                        EqualExp '==' RelExp |
                        EqualExp '!=' RelExp

RelExp              ::= ShiftExp |
                        RelExp '<' ShiftExp |
                        RelExp '>' ShiftExp |
                        RelExp '<=' ShiftExp |
                        RelExp '>=' ShiftExp

ShiftExp            ::= AddExp |
                        ShiftExp '<<' AddExp |
                        ShiftExp '>>' AddExp

AddExp              ::= MulExp |
                        AddExp '+' MulExp |
                        AddExp '-' MulExp

MulExp              ::= PmExp |
                        MulExp '*' PmExp |
                        MulExp '/' PmExp |
                        MulExp '%' PmExp
    
PmExp               ::= CastExp |
                        PmExp '.*' CastExp

CastExp             ::= UnaryExp |
                        '(' TypeId ')' CastExp

UnaryExp            ::= PostfixExp |
                        '++' CastExp |
                        '--' CastExp |
                        UnaryOp CastExp
                        
PostfixExp          ::= PrimaryExp |
                        PostfixExp '[' Expression ']' |
                        PostfixExp '(' Expression ')' |
                        PostfixExp '(' [ ExpList ] ')' |
                        SimpleTypeSpec '(' [ ExpList ] ')' |
                        PostfixExp '++' |
                        PostfixExp '--'

PrimaryExp          ::= Literal |
                        '(' Expression ')' |
                        IdExp

IdExp               ::= UnqualifiedId

ExpList             ::= AssigmentExp |
                        ExpList ',' AssignmentExp
                        
//////////////////////////////
//Identifier
//////////////////////////////
DeclId              ::= IdExp |
                        TypeName

UnqualifiedId       ::= Identifier

Identifier          ::= NonDigit |
                        Identifier NonDigit |
                        Identifier Digit

//////////////////////////////
//Literals
//////////////////////////////
Literal             ::= IntLiteral |
                        FloatLiteral |
                        BoolLitreral

IntLiteral          ::= DemicalLiteral

DemicalLiteral      ::= NonZeroDigit |
                        DemicalLiteral | Digit
    
FloatLiteral        ::= FracConstant [ExponentPart] |
                        DigitSeq ExponentPart
                        
BoolLiteral         ::= 'false' |
                        'true'

FracConstant        ::= [DigitSeq] '.' DigitSeq |
                        DigitSeq '.'
                        
ExponentPart        ::= 'e' [Sign] DigitSeq |
                        'E' [Sign] DigitSeq
                        
DigitSeq            ::= Digit |
                        DigitSeq Digit
                        
//////////////////////////
//Terminals
//////////////////////////

NonDigit            ::= AlphaChar |
                        '_'

NonZeroDigit        ::= '1' |  | '9'

AssignmentOp        ::= '=' | 
                        '*='  | '/='  | '%=' |
                        '+='  | '-='  |
                        '>>=' | '<<=' |
                        '&='  | '^='  | '|='
Register
Semantic
Digit
AlphaChar
Keyword

有点儿参差不齐，哈哈。一些Terminator我就没有写了。预处理的部分由于使用Boost.Wave，因此也没有加入到EBNF中。这些都很大程度上简化了EBNF的内容。
然后大概的根据层次归了一下类，看起来要方便一点。
但愿语法树里面没有漏掉的。
等回到自己机器上就开始自下向上的实现这个东西了，争取10月份之前能把整个Shader编译器集成到SoftArt里面去。
目前就让它在SVN的SandBox里面待着好了。

空明流转 2008-07-25 02:25 发表评论

开始写EBNF Grammar for SoftArt Shader Language

空明流转 — Thu, 24 Jul 2008 16:11:00 GMT

最近在做Shader的编译器。

想好了我的编译器就叫SASL，SoftArt Shader Language。
因为之前没写过EBNF，没什么经验，因此找了C和C++的EBNF在参考。
特别是C的EBNF。
因为可以用LALR(1)实现，因此对我这样用LEX + YACC的人而言就更加有用一点。
整体而言准备尽可能和SM4.0一致，用Boost.Wave支持Preprocessing。
这样的话差不多就全了。这两天先把Shader的EBNF弄出来，完了开始从小往大写慢慢写语法分析器和编译器。

http://www.externsoft.ch/download/cpp-iso.html

这里是C++的EBNF。有点太复杂了觉得。。。

空明流转 2008-07-25 00:11 发表评论

再用Boost.Python

空明流转 — Mon, 14 Jul 2008 11:05:00 GMT

上次用boost.python的时候boost还是1.33的时候。

那个时候刚刚开始看shader的东西，就用boost.python做了用python做shader语言的演示。
其实当时看boost.python完全是半懂不懂的。
这段时间找了个C的数值库，要Python的接口，Python For C的Interface又懒得使用，还是用boost.python把一些我要的功能给封装出来好了。
结果一看才发现对Boost.Python的理解好了不好。

看来人都是在慢慢进步的。。。哈哈。

空明流转 2008-07-14 19:05 发表评论

一个3D骨骼动画 2D版超精简Demo，原理和实现几乎同3D一致

空明流转 — Sat, 07 Jun 2008 11:35:00 GMT

以前看D3D的时候，就发现骨骼动画是个有点难以掌握的东西。
但是也可以说，骨骼动画是3D齐次空间变换的集大成者，掌握了骨骼动画，差不多3D空间变换你也就掌握了。
其他所有的层级变换，基本上都不会脱离骨骼动画需要你了解的东西。

网上骨骼动画的demo多如牛毛，我空间想象能力不行，看过无数资料都不大明白骨骼怎么转，皮肤怎么蒙。况且那些基于DX、基于GL的代码都长的不行，难看的明白。

前两天vczh搞了个C#的弱智版的2D物理Engine，我今天就搞个C#和GDIPlus的低能版骨骼变换。虽然是2D的，但是原理和实现基本和3D的完全一样。希望这已经简单到不能再简单的代码能帮助大家搞明白骨骼动画是咋回事。

代码框架上都有注释了，矩阵使用的是Sharp3D的数学库，已经在包中了。不过也就用了矩阵乘法和矩阵-矢量乘法，还有一些矢量加减法。

源代码在此下载。

2楼的回帖给了一个地址，是关于骨骼运动变换的数学推理和理论解释，还讨论了左右手系的问题。理论上有问题的亲们可以参照此篇文章。

截图：

骨骼的初始状态

变换后的骨骼

加了一圈子顶点，这个虽然是2D的，但也是货真价实的蒙皮哈。

空明流转 2008-06-07 19:35 发表评论

GPU Gems 3 Chapter 3 List 3.4的解释

空明流转 — Wed, 21 May 2008 02:58:00 GMT

1 for(int i=0; i<numBS; i++)
2 {
3   uint offset = bsPitch * bsOffsets.Load(i);
4   float weight = bsWeights.Load(i);
5   dp = bsVertices.Load(offset + 3*vertexID+0);
6   dn = bsVertices.Load(offset + 3*vertexID+1);
7   dt = bsVertices.Load(offset + 3*vertexID+2);
8
9   pos += dp * weight;
10   normal += dn * weight;
11   tangent += dt * weight;
12 }
13

Blend Shapes 放在一个固定的数组bsVertices中,
按照

S0V0, S0V1 ... S0VN, S1V0 ... SMVN
的形式存放.

numBS说明了有多少个BS被混合，也就是slots的大小;
bsPitch为SxV0 - SxVN的长度;
bsOffsets[i] 代表第i个slot使用了哪个BS.

空明流转 2008-05-21 10:58 发表评论

开个新的系列：GPU Gems 3 导读 + Chapter I 运用GPU构造复杂的过程化地形导读（上）

空明流转 — Tue, 20 May 2008 12:38:00 GMT

最近开始抽空在看GPU Gems 3了。本来想挑几篇全文翻译，但是无奈自己英语水平薄弱，同时最近老板逼得紧，也没有那么多时间，于是便准备以导读的形式，将文章的主干部分翻译出来,帮助英文不好的筒子们。
导读也是我自己读书的总结。文章的核心内容一定会提及.图和源码，通常我会标注上对应的图书上的figure和list，各位自行参考。基本维持原文的篇章段落，但是一般不会逐字句的考究。
至于能有多少篇，我倒是不能保证。不过我所用的电子版是那个26M的chm，我读的时候会把它翻成PDF并加注，如果有筒子需要我注释后的pdf，可以与我联系：

mail： wuye9036 _AAAAATTTTT_ google _dotdotdotdotdot_com

--------------------------------------------------------------------------------

Chapter I 运用GPU构造复杂的过程化地形
1.1 Introduction
过程化地形的应用已经有不少的历史了，Game Programming Gems 2上就已经有了不少成熟的过程化地形的方法，比方说随机断层、基于噪声的、基于分形理论的、中点分割加扰动的。
不过这些算法在现代硬件上都时有缺陷的，特别是针对规模很大的地形，要么只能在CPU上实时生成，要么就得预存储起来，但是不管怎么说都面临着很大的资源开销；其次这些算法都是只能生成有些起伏的平面，没办法表现山洞、岩石凸角一类的3D特征。本文运用DX10的Geometry Shader与Stream Output，弥补了上述两个缺陷。

1.2 移动立方体与密度函数
要解决3D的地形特征，首先要解决3D地形特征的表达问题。文中将空间划分为多个Blocks，每个Block代表了世界坐标系中1*1*1大小的空间。每个Block由一个3D纹理来表达。由于使用了过程化的方法，每个Block可以在运行的时候动态生成，这样只需要保留那些能看得见的blocks，从而解决了存储问题。
概念上，一个3D的地形可以由一个密度函数来表达。对于每个空间中的点(x, y, z)，都有唯一对应的密度值。我们假设，对于任意一个空间中的点，如果点在地形内部/岩石内部当且仅当点上的密度值大于0。那么小于0的点，自然就在地形之外，如在空气中，水中等等。而岩石表面上的点密度刚好等于0。
那么自然，这些岩石表面上密度值等于0的点，就是我们要绘制的“表面”。
在将空间划分为Block后，还要将每个block进一步细分为多个voxel（体素）。我们假定体素内密度变化时连续的。那么很显然，如果一个体素的顶点上密度有正有负，那么必然里面会有一个（也有可能是多个）0值面。问题就转化为，如何根据体素各个顶点的密度值，求出这个体素内的0值面。如果再把这个假设限定的严格一点，如果体素内密度变化是线性的，那么这些面可以由0-5个三角形来表示；求得这些三角形的方法，被称为Marching Cube算法。
很显然，有多少个三角形，每个三角形的顶点落在哪条边上，是由八个顶点的密度的正负值所决定的，而值的相对大小则决定了三角形的顶点在边上靠近那个顶点。那么也就是说，一个体素内0值面的分布共有2^8中情况。如果顶点密度为负，那么标记为0，顶点密度为正则标记为1，则八个顶点的情况可以由一个Byte来表示。

图1-3

如果这个字节的值为0或者为255，那么说明所有的顶点都为正或为负，那么说明体素中并没有地表面。Martin Frank为剩下的254中情况建立了一个查找表。其中基本的情形有14种，其余的均可由这些基本情况的对称或旋转求得。

图1-4

当确定了三角形的三个顶点分布于哪些边上后，便可用插值的方法求出所在位置。顶点将位于0值点处。例如，一条边AB上有一个0值点P，如果A的密度0.3，B的密度-0.1，那么PB的长度是PA长度的三倍。

1.2.2 查找表
上文已经提到了如何通过体素角点的密度值，就会知道会生成哪些多边形；这些多边形的顶点落在哪些边上。
接下来，我们将用讨论这些理论如何在GPU上实现。
首先我们建立一张查找表
int case_to_numpolys[256];
其中每种情况能产生多少个三角形。
第二张查找表，
int3 edge_connect_list[256][5];
这张表保存了每种情况对应的5个三角形。并且我们将一个体素中的12条边按照0-11编号（图 1-5），则查找返回的返回的int3指出了，每个三角形的三个顶点分别落在哪条边上。

图 1-5 Case 193 的0值多边形情况

下面的例子很好的说明了这一点。
我们以case 193为例。193总共有3个三角形，那么case_to_numploys[193] = 3，其次，edge_connect_list[193][]返回这样的结果：

int3 edge_connect_list[193][0]: 11 5 10
int3 edge_connect_list[193][1]: 11 7 5
int3 edge_connect_list[193][2]: 8 3 0
int3 edge_connect_list[193][3]: -1 -1 -1
int3 edge_connect_list[193][4]: -1 -1 -1

Geometry Shader在查找了这两张表的信息之后，并计算出顶点在边上的具体位置，便会返回3个多边形列表所需要的9个顶点。由于创建Marching Cubes查找表需要很多的计算量，因此建议预先计算好并在运行前载入。该表在光盘上可以找到。

空明流转 2008-05-20 20:38 发表评论

脚本编程琐话

空明流转 — Fri, 16 May 2008 07:51:00 GMT

摘要:
讨论脚本编程与静态语言的异同点，
总结一下近期脚本编程的心得，
吸取教训，
并欢迎大家探讨、指点。阅读全文

空明流转 2008-05-16 15:51 发表评论

一个type2id的程序

空明流转 — Fri, 07 Mar 2008 16:55:00 GMT

这个设计主要是拿来保证跨组件的时候能尽可能的保护型别安全.

我今天晚上早些时候也往SoftArt里面提交了一个type to id的实现,使用宏和特化机制
但是这个版本的一个很大的问题就在于用起来不是很方便,每注册一个类需要2行代码,而且都是
#define PARAM float
#include REGTYPE()
这样的非常规的宏用法.
但是由于它是分类实现的,所以可以在里面补充一些额外的功能,比如自动的具名常量的生成.

所以晚上回来的时候又用boost的mpl写了一个原形,基本上是纯模板的.注册类只需要一行,但是宏实现版本中一些半自动化的特点也损失的差不多了.
回头还是要考虑用preprocessor结合MPL,看看能不能做到两个特点兼备.

mingw + gcc 4.2.1下通过

#include <iostream>
#include <boost/smart_ptr.hpp>

#include <boost/mpl/vector.hpp>
#include <boost/mpl/find.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/less.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/less_equal.hpp>

#include <boost/type_traits/is_same.hpp>

using namespace std;

struct empty{};

#define BEGIN_REGISTER_TYPE() typedef boost::mpl::vector
#define REGISTER_TYPE(type) ,type
#define END_REGISTER_TYPE() > typelst;

namespace shader_constant
{
    BEGIN_REGISTER_TYPE()
        REGISTER_TYPE(int)
        REGISTER_TYPE(float)
        REGISTER_TYPE(bool)
    END_REGISTER_TYPE();

    static const int size_of_typelst = boost::mpl::size<typelst>::value;
    typedef boost::mpl::int_<size_of_typelst> size_of_typelst_t;

    template<class T>
    struct type2id{
        typedef typename boost::mpl::find<typelst, T>::type iter;
        static const int id =
            boost::mpl::if_<
                boost::is_same<boost::mpl::end<typelst>::type, iter>,
                boost::mpl::int_<0>,
                typename iter::pos
            >::type::value;
    };

    template<int id>
    struct id2type{
        typedef boost::mpl::int_<id> int_id;
        typedef boost::mpl::int_<0> int_0;

        //type = (0 < id && id <= size) ? typelst[id] : empty;
        typedef typename boost::mpl::if_<
            boost::mpl::and_<
                boost::mpl::less<int_0, int_id >,
                boost::mpl::less_equal<int_id, boost::mpl::size<typelst>::type >
            >,
            typename boost::mpl::at<typelst, int_id>::type,
            empty
        >::type type;
    };
}

using namespace shader_constant;

typedef void (*Assignments)(void* p1, void* p2);

template<class T>
void AssignImpl(void* p1, void* p2)
{
    cout << typeid(T).name() << endl;
    *(T*)p1 = *(T*)p2;
}

template <> void AssignImpl<empty>(void* p1, void* p2)
{
    cout << "error type!" << endl;
}

Assignments assigns[size_of_typelst+1];

template <int i>
struct assigns_initializer
{
    assigns_initializer<i-1> m;
    assigns_initializer(){
        assigns[i] = &AssignImpl<typename id2type<i>::type >;
        }
};

template <>
struct assigns_initializer<-1>
{
    assigns_initializer(){
        }
};

static assigns_initializer<size_of_typelst> ai;

typedef double T;
int main()
{
    T i1(T(0));
    T i2(T(10));
    assigns[type2id<T>::id](&i1, &i2);
    cout << i1;
    system("pause");
    return 0;
}

空明流转 2008-03-08 00:55 发表评论

软件渲染器的项目已经在SF.NET上了

空明流转 — Wed, 20 Feb 2008 10:44:00 GMT

2月22日更新：
修改了项目设置（大换血。。。）。昨天下过的最好重新check out。

2月21日更新：

已经将SoftArt整体放置到SF的SVN上了。

SVN地址： https://softart.svn.sourceforge/svnroot/softart/prealpha
svn co https://softart.svn.sourceforge/svnroot/softart/prealpha softart

由于目前的渲染器离成品还很遥远，所以就没有以Release的形式放出。Version 6 中，CartoonDemo大家可以自行从solution里面移除；EFLIB需要项目地址上下载Release，然后在VC环境中另行设置，给大家带来的不便深表歉意。

2005 SP1 下通过（有点bug）

感谢亨德列克和叛逆者两位前辈的无私指点（不管哪一方面都是，从技术到态度到Fix Defects到New Ideas），非常感谢～～～拜～～～

该软件渲染器名字就叫SoftArt，本来准备叫做ColorfulSnail（哈，因为Debug的时候它的运行速度是在是太慢了），但是无奈Snail已经被人注册过了，所以就还是叫这个名字了。
每个开发阶段我都会有一个项目代号，目前的这个还是prealpha阶段，所以就叫prealpha好了。

今天放上去的是支持库Essential Functions Library，大家可以去我的项目地址下载。

https://sourceforge.net/projects/softart/

也叫Efl Functions Library，提供了一些基本的数学工具（比方说基本的向量和矩阵的运算）。项目的主体代码我需要将接口整理完毕以后再行发布。目前仅https://softart.svn.sourceforge.net/svnroot/softart/prealpha 支持VS2005编译器，很快会考虑2008和GCC 4.2 or later。

希望大家有什么意见和建议尽管提出，我一定会尽可能将大家的想法加入到我的TODO LIST中。

空明流转 2008-02-20 18:44 发表评论

设计模式小结（三）

空明流转 — Sun, 17 Feb 2008 07:11:00 GMT

摘要: 总结了我在以往项目中使用设计模式的经验；
我阅读《设计模式》的心得；
讨论一些在阅读时产生，实践中解决的困惑，为设计模式新手提供一条可以参考的学习路线；
并希望与老手们一同探讨、交换：
设计模式在实际中使用中的经验与教训；关于拓展现有设计模式、联合使用多个设计模式的案例和思路。阅读全文

空明流转 2008-02-17 15:11 发表评论