[UGUI]ugui中同一batch的遮挡顺序

前言

最近被人问到同一batch中ugui的前后顺序是怎么表现出来的,之前我只考虑过一帧是怎么前后顺序的渲染,所以这次我讲说一下一个batch中的图片渲染顺序

知识点

  1. 使用xcode的FPS截帧
  2. 渲染的点的坐标
  3. 渲染三角形的顺序
  4. 渲染三角形的uv顺序

正文

渲染图片的本质

在一般情况下,我们常说的渲染一张图片其实是记录下一张图片的四个顶点位置,通过mvp变换,从模型空间转换到屏幕空间,然后渲染到显示设备上。在渲染的时候,我们需要定义三角形的顺序,根据对应渲染设备所使用的坐标系,我们通过左手或者右手定则,来确定渲染的朝向。定义的uv坐标来确定这三个点所需要渲染的颜色在uv图上的什么位置。通过上面的概念我们就应该能知道渲染一个图所需要简单的数据结构了。

我们只考虑最上面的那张图我们来简单定义一下数据结构

vector3[]index   --点坐标
int[2*3] vertex     --三角形的渲染顺序
int[2*3] UV             --uv坐标id

通过上面的结构体,我们就能正常的渲染出一张图片出来的。

ugui合批本质

我这里所说的合批是ugui的动态合批。一般来说,你可以认为它就是问了把多个mesh合并成一个mesh传到gpu去渲染,那什么是mesh呢?其实就是我们上面所说的那个结构体。既然知道了它是什么,我们就好来理解mesh的合并了。首先在ugui我们会对渲染的物体进行一次排序(这个内容我已经拖更很久了,大家可以去看官方的一节课)然后通过这个排序结果,我们就可以开始记录合并的mesh内容了。如果是同一个材质,同一个贴图,并且是相邻的,那就记录一次合并,如果不可以,那就把上一次合并的结果callback到gpu做一次渲染,剩下的再进行合并记录。

同一批次的遮挡顺序

通过上面我们就可以知道,同一个批次里面,如果图片前后有遮挡关系;首先我们通过排序,记录下所有点的位置信息,然后通过顺序我们记录下来三角形的渲染顺序

在这张图片,我们就能看出来,其实在这个批次的渲染里,我们是记录下来所有点,和所有三角形的信息给gpu去渲染的,在这次合批中我们是不会进行三角形的剔除操作。就算是所有做了一次完全的遮挡,其实我们上传的数据也是做了一次全量的记录的。所以同一batch的遮挡就是在合批时候的排序顺序的关系。

总结

渲染的本质是通过三角形的排布来做纹理的展示,所有的优化方式都是围绕这三角形怎么减少呀,三角形的颜色该怎么计算出来,这样的方式来做优化的。了解本质,你才能更轻松的理解方案。

[XLua]lua和c#交互

前言

在移动游戏发展到今天,热更技术已经有很多种渠道了,一种是使用lua,一种是c#更新dll,还有最新出来的TypeScript的热更新。这次我就简单的聊些使用率最多的lua热更新中的交互,也希望能说出一些交互上可以优化的东西。

知识大纲

  1. 函数
  2. 值类型
  3. 引用类型
  4. struct类型
  5. string类型
  6. lua和c的交互调用栈
  7. IntPtr类型

初始化

获取全局表

在lua初始化的时候会初始化一个luaEnv对象,他会去c里拿到一个LUA_REGISTRYINDEX这是一个registry的表的索引,这个表是c可以自由使用,但是lua代码不能访问他。

注册lua状态机

使用luaL_newstate创建了一个新的lua状态机(可以理解为lua虚拟机),主要用来为每一个lua线程创建独立的函数栈和线程栈,以及lua所需要的内存管理,字符串管理,gc管理。创建两个主要的数据结构lua_state和global_State。

  • lua_State:主线程栈结构
  • global_State:全局状态机,维护全局字符串,内存管理函数,gc等信息

加载lua标准库

使用luaL_openlibs用来加载lua的标准库到指定的lua状态机。

注册一个用来lua和c#交互的对象

通过创建一个ObjectTranslator对象来做lua和c#的对象交互,传入一个luaEnv对象,和一个lua状态机的指针。创建了一个弱value的一个table放在lua中。注册lua对象回收中__gc的回调方法。使用lua_pushlightuserdata创建一个自己管理的xlua标志位。注册所有被此应用所用的所有程序集到assemblies中

注册xlua全局表

translator.OpenLib(rawL);
import_type这个方法为lua中获取全局c#方法的回调函数

注册一个lua异常捕获

LuaAPI.lua_atpanic(rawL, StaticLuaCallbacks.Panic);使用这个方法注册一个在c#中去处置lua程序崩溃的方法

注册一个lua的print方法

LuaAPI.lua_pushstdcallcfunction(rawL, StaticLuaCallbacks.Print);LuaAPI.xlua_setglobal(rawL, "print")
注册一个print的方法注册到global全局表中的print

初始化Init脚本

注册一个全局的CS表,设置CS的元方法。设置xlua的元方法。

获取_G全局表

LuaAPI.xlua_getglobal(rawL, "_G");translator.Get(rawL, -1, out _G);获取_G

注册类

通过Wrap中的__Register的方法用来注册当前这个类的实例化函数,静态函数,属性,静态属性,实例化类的方法

注册函数

通过BeginObjectRegister在栈顶注册一个class.FullName名字的metatable表。给他塞入一个xlua的标志,覆盖两个关于“gc”和“tostring”的元方法。创建三个table,用来存放类的函数,设置属性方法,获取属性方法。调用RegisterFunc把所需要的函数方法注册进去。最后在结束的时候替换掉“index”和“newIndex”这两个元方法

注册静态函数

通过BeginClassRegister中把当前类的静态函数注册到table中,然后通过SetCSTable把当前类名的table放在cstable下,然后替换元方法__call为c#的函数,最后创建两个table用来放置静态属性;还是通过RegisterFunc把静态属性的获取和设置添加进去。

加载lua脚本

DoString

通过xluaL_loadbuffer编译lua脚本,通过lua_setfenv设置当前lua编译脚本为传进来的table的upvalue值,然后通过Lua_pcall执行编译之后的脚本,放回栈顶的对象。

Lua和c#交互

c#调用lua方法

在DoString之后把DoString所执行的脚本设置到一个luatable对象里面,然后通过这个luatable对象去lua栈里拿到luatable所在的table。在tryGetGetFuncByType发现我们要转换的类型不是我们定义的那些基础类型,所以通过GetObject去获取到一个转换委托ObjectCast这个委托函数里,然后通过需要转换到类型调用不同的转换函数,函数就是通过调用CreateDelegateBridge来创建一个action委托的,委托里包含了lua方法的索引。当函数调用的时候就是调用委托里的PCall来调用到lua中的方法。因为在tryGetGetFuncByType没有注册,所以使用了反射去创建当前类型的对象。

c#获取lua值类型

也是在tryGetGetFuncByType里把int ,bool,float这的值类型通过从lua栈里push出number,boolean,integer的值通过类型转换变换出来。

c#获取lua的table类型

当把table定义成一个list对象的时候,它也和调用函数一样回去判断有没有在tryGetGetFuncByType里定义了这个list类型的ObjectCast,如果没有也是通过反射在genCaster里去创建这个对象,把lua栈内的值取出来。

c#获取lua的string

当需要在lua中使用到c#的string时,把string转成byte[]传到lua中。
当把lua中的string传到c#的时候,也是把string转成byte[]接收过来,转成string

lua调用函数

在init的时候生成的时候会设置import_type为CS的index方法中的查找到c#里的ImportType去根据className去translator.FindType找到当前这个className到类型,然后通过GetTypeId去找放回类型的唯一id,如果这个类型没有缓存,那就会去生成一个当前类型名字的metatable,然后通过DelayWrapLoader中注册的loader去加载生成的wrap类的Register生成的当前所需要的方法的metatable,给lua调用,然后把类型的id传到交互栈中。当调用这个方法的时候就可以通过在RegisterFunc的时候push进去的lua_pushstdcallcfunction来掉到这个函数了。

lua调用值类型

当lua需要设置值类型的时候,同样会定义一个属性赋值方法,通过函数调用的方法调用到这个方法,然后通过lua_tointeger去栈里拿到这个方法一起传过来的number类型的值,然后赋值过去。
当lua需要设置值的时候,还是定义一个属性获取的方法,通过函数调用先通过Get方法从userdata中获取到这个需要赋值的对象,然后通过UnPack来把这个需要赋值的属性取出来,然后修改掉对应的属性;最后通过push把属性塞到lua栈中

lua调用struct类型

当lua需要获取一个struct类型的值时,因为lua中没有struct这样的结构类型所以会把struct包成一个object传到lua栈中当userdata存下来。
当lua需要设置一个struct类型的值时,获取到栈内的userdata然后存成ObjectCast然后转成struct,取lua栈内第二个参数来设置struct的值

但是在xlua中vector和color这两种struct会做一次处理,会把里面的struct的结构内容给拆分出来,通过基础的值类型进行传递。

lua调用引用对象

通过addObject把创建出来的object存在objecttranslator中,返回一个存放的index,然后把这个index传到xlua_pushcsobj里去创建一个userdata并且把这个对象的方法,属性都传进去做metatable属性。然后就可以获取到这个userdata赋值给lua。

lua和c#相互引用对象的生命周期

通过上面知道在c#中需要被lua所调用到的引用类型对象都需要在objecttranslator中存起来,然后把所生成的index传到lua的userdata中去,然后给这个userdata设置了一个元表,修改了gc这个元方法,所以当lua的userdata不在被引用的时候就会触发lua的gc,然后调用到gc这个元方法,调用到ObjectTranslator中的collectObject然后保存列表中清理掉。
在c#获取到lua的对象需要创建一个object的对象,然后把lua中的reference通过luaL_ref获取到保存下来,然后当这个对象不在被引用的时候,调用到c#的dispose函数,然后在里面去LuaAPI.lua_unref释放掉这个lua对象的引用。

总结

通过上面的数据交互,我们可以知道,在lua和c#的交互,我们需要注意到引用类型的交互,因为他们会分别在lua端和c#端创建一个objcet和table(userdata)对象,而这两种对象都会产生gc压力,还有一个就是struct对象也是需要注意的,虽然在xlua中vextor会拆成基础值类型传递,但是大部分我们自定义的struct还是会被包装成一个object传递的,这里还产生了一个装箱操作,所以消耗会更大。

【编程基础】c#中的List源码解析

前言

我们在使用一些组件的时候,很容易在不了解它底层实现的情况下,使用出一些性能的问题。作为一个良好的程序员来说,能在在遇到这种问题的时候给出解决方案,算是一个基本的职业素质。所以我们需要在使用组件的时候知其所以然。

为什么需要了解List

List 这个组件是一个可伸缩的数组组件,我们会常常用它来代替数组,因为是可伸缩的,所以我们使用的地方太多了。

需要了解哪些东西

  1. 增加元素
  2. 删除元素
  3. 修改元素
  4. 怎么伸缩(这个其实在上面应该会说)

源码地址

正文

构造部分

首先我们来看下List的构造部分,源码如下:

public class List<T> : IList<T>,System.Collections.IList,IReadOnlyList<T>
{
    private const int _DefaultCapacity = 4;
    private T[] _items;
    [ContractPublicPropertyName("Count")]
    private int  _size;
    private int _version;
    [NoSerialized]
    private Object _syncRoot;
    static readonly T[] _emptyArray = new T[0];
    public List(){
        _items = _emptyArray;
    }
    public List(int capacity){
        if(capacity<0) ThrowHelper.ThrowArgumentOutOfRangeException(ExcptionArgument.capacity,ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
        Contract.EndContractBlock();
        if(capacity == 0)
            _items = _emptyArray;
        else
            _items = new T[capacity];
    }
    public List(IEnumerable<T> collection){
        if (collection==null)
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
            Contract.EndContractBlock();
            ICollection<T> c = collection as ICollection<T>;
            if( c != null) {
                int count = c.Count;
                if (count == 0)
                {
                    _items = _emptyArray;
                }
                else {
                    _items = new T[count];
                    c.CopyTo(_items, 0);
                    _size = count;
                }
            }
            else {
                _size = 0;
                _items = _emptyArray;
                using(IEnumerator<T> en = collection.GetEnumerator()) {
                    while(en.MoveNext()) {
                        Add(en.Current);
                    }
                }
            }
        //...
        //其他内容
    }
}

从源码中我们可以知道,List继承IList,和IReadOnlyList这两个接口,IList是提供主要的接口,IReadOnlyList提供了迭代接口。
我们还能知道List内部是用数组来实现的,它有三种构造方法,一个是啥都不传的,默认初始化一个长度0的数组,一个是初始化数组长度的构造函数,一个是复制给定集合内容的构造函数,长度和内容都和传进来的数组一样。

添加

当我们看到第三种构造函数的时候,我们会发现最下面有一个Add这个函数的调用,这个函数就是List中添加。
源码如下:

public void Add(T item){
    if(_size == _item.Length) ExsureCapacity(_size + 1);
    _item[_size++] = item;
    _version++;
}
private void EnsureCapacity(int min){
    if(_item.Length < min){
        int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
        if((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if(newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}
public int Capacity{
    get{
        Contract.Ensures(Contract.Result<int>() >= 0);
        return _item.Length;
    }
    set{
        if(value < _size){
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }
        Contract.EndContractBlock();
        if(value != _items.Length){
            if(value > 0){
                T[] newItems = new T[value];
                if(_size > 0){
                    Array.Copy(_items,0,newItems,0,_size);
                }
                _items = newItems;
            }else{
                _items = _emptyArray;
            }
        }
    }
}

从上面的源码我们可以看出来,当List在Add一个item的时候,会先去判断这个数组是不是已经满了,如果满了就拓容,从4,16,32 ...n(上一次数组大小)*2 这样的大小来拓容的,当拓容之后,会新建一个新的数组,把原来数组内容给拷贝进去,然后再去添加新的元素。

  1. 如果你直接调用Capacity赋值数组商都为负数的时候,你会出现数组被清理成默认的,但是数组的标记size(这个代表当前添加到数组第几个位置)却没有清空,下一次你要用的时候,会浪费之前那么多的内存空间。

  2. 当你在添加一堆数据的时候(例如128个数据)在一开始没有给List赋值长度的话,它就会在你添加的时候进行六次扩容,然后这六次扩容中有五次是需要拷贝元素数据的,这样每次拷贝都会造成新的内存垃圾,这样就会给GC带来很多负担。

  3. 如果添加的数量不得当,也会照成内存空间的浪费,比如元素数量为520的时候,List就会扩容到1024个元素,这样就会多出502个空间单位没有被使用。

删除

删除我们主要看Remove这个函数
源码如下:

public bool Remove(T item){
    int index = indexOf(item);
    if (index>=0){
        RemoveAt(index);
        return true;
    }
    return false;
}
public int indexof(T item){
    Contract.Ensures(Contract.Result<int>() >= -1);
    Contract.Ensures(Contract.Result<int>() < Count);
    return Array.IndexOf(_items,item,0,_size);
}
public void RemoveAt(int index){
    if((uint)index >= (uint)_size){
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    Contract.EndContractBlock();
    _size--;
    if(index < _size){
        Array.Copy(_items,index+1,_items,index,_size-index);
    }
    _item[size] = default(T);
    _version++;
}

Remove接口中包含了IndexOf和RemoveAt,这两个方法,IndexOf是为了定位要删除的元素的位置,这个接口的实现是按索引从0到n个位置做意义比较,时间复杂度为O(n);RemoveAt这个方法是用来删除指定位置的元素,但是它的实现是用Array.Copy来进行数组的覆盖。

插入

源码如下:

public void Insert(int index,T item){
    if((uint) index > (uint)_size){
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
    }
    Contract.EndContractBlock();
    if(_size == _items.Length) EnsureCapacity(_size + 1);
    if(index < _size){
        Array.Copy(_items,index,_items,index+1,_size-index);
    }
    _items[index] = item;
    _size++;
    _version++;
}

从源码中我们可以看到,Insert和Add接口一样,都会先检查容量是否足够,如果不够就扩容,插入的位置是否是数组的最后,如果不是进行数组拷贝,将index后面的元素集体后移一位。
在这里我们可以很清楚一个概念,就是最坏的情况下,我们插入一个数据需要做2次数据拷贝,会造成GC时的压力。

思考

其他相关的接口比如AddRange,RemoveRange,InsertRange的原理其实和Add,Remove,Insert一样,区别就是从单个元素变成以容易为单位的操作,都是做一些重复覆盖的操作,和扩容。他们没有进行任何形式的优化,都是使用顺序迭代的方式。如果频繁调用,会照成不小的内存冗余和GC的压力。

其他的一些接口说明

比如[]的实现

public T this[int index] {
            get {
                // Following trick can reduce the range check by one
                if ((uint) index >= (uint)_size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException();
                }
                Contract.EndContractBlock();
                return _items[index]; 
            }

            set {
                if ((uint) index >= (uint)_size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException();
                }
                Contract.EndContractBlock();
                _items[index] = value;
                _version++;
            }
        }

这个就是直接使用数组的的索引方式来获取元素,赋值元素,

Clear清除接口

public void Clear() {
            if (_size > 0)
            {
                Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
                _size = 0;
            }
            _version++;
        }

调用的时候不会去删除数组内的元素,只是将元素清零,然后设置_size为0;

Contains接口

public bool Contains(T item) {
   if ((Object) item == null) {
                for(int i=0; i<_size; i++)
                    if ((Object) _items[i] == null)
                        return true;
                return false;
            }
            else {
                EqualityComparer<T> c = EqualityComparer<T>.Default;
                for(int i=0; i<_size; i++) {
                    if (c.Equals(_items[i], item)) return true;
                }
                return false;
            }
        }

我们看到它就是做了一次线性比较的方式来对数组进行迭代查找,并且返回的是第一个比对上的元素。

ToArray接口

public T[] ToArray() {
            Contract.Ensures(Contract.Result<T[]>() != null);
            Contract.Ensures(Contract.Result<T[]>().Length == Count);

            T[] array = new T[_size];
            Array.Copy(_items, 0, array, 0, _size);
            return array;
        }

它的实现就是新建一个数组,然后把元素拷贝进去再返回出来。

Find 接口

 public T Find(Predicate<T> match) {
            if( match == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            Contract.EndContractBlock();

            for(int i = 0 ; i < _size; i++) {
                if(match(_items[i])) {
                    return _items[i];
                }
            }
            return default(T);
        }

同样适用的是线性查找,对每个元素都进行比较,时间复杂度为O(n).

Enumerator 迭代的实现

public Enumerator GetEnumerator() {
            return new Enumerator(this);
        }
IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            return new Enumerator(this);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return new Enumerator(this);
        }
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
        {
            private List<T> list;
            private int index;
            private int version;
            private T current;

            internal Enumerator(List<T> list) {
                this.list = list;
                index = 0;
                version = list._version;
                current = default(T);
            }

            public void Dispose() {
            }

            public bool MoveNext() {

                List<T> localList = list;

                if (version == localList._version && ((uint)index < (uint)localList._size)) 
                {                                                     
                    current = localList._items[index];                    
                    index++;
                    return true;
                }
                return MoveNextRare();
            }

            private bool MoveNextRare()
            {                
                if (version != list._version) {
                    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                }

                index = list._size + 1;
                current = default(T);
                return false;                
            }

            public T Current {
                get {
                    return current;
                }
            }

            Object System.Collections.IEnumerator.Current {
                get {
                    if( index == 0 || index == list._size + 1) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    }
                    return Current;
                }
            }

            void System.Collections.IEnumerator.Reset() {
                if (version != list._version) {
                    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                }

                index = 0;
                current = default(T);
            }

        }

我们可以看到Enumerator这个接口在每次被获取的时候都是new出来的,如果使用大量的迭代器的时候就会有大量的对象,照成GC压力

Sort接口

public void Sort()
        {
            Sort(0, Count, null);
        }
 public void Sort(IComparer<T> comparer)
        {
            Sort(0, Count, comparer);
        }
public void Sort(int index, int count, IComparer<T> comparer) {
            if (index < 0) {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }

            if (count < 0) {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }

            if (_size - index < count)
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            Contract.EndContractBlock();

            Array.Sort<T>(_items, index, count, comparer);
            _version++;
        }

        public void Sort(Comparison<T> comparison) {
            if( comparison == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            Contract.EndContractBlock();

            if( _size > 0) {
                IComparer<T> comparer = new Array.FunctorComparer<T>(comparison);
                Array.Sort(_items, 0, _size, comparer);
            }
        }
// Array.Sort
internal void Sort(int left, int length)
            {
#if FEATURE_CORECLR
                // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade 
                // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka 
                // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.

                IntrospectiveSort(left, length);
#else
                if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
                {
                    IntrospectiveSort(left, length);
                }
                else
                {
                    DepthLimitedQuickSort(left, length + left - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
                }
#endif
            }
             private void DepthLimitedQuickSort(int left, int right, int depthLimit)
            {
                // Can use the much faster jit helpers for array access.
                do
                {
                    if (depthLimit == 0)
                    {
                        // Add a try block here to detect IComparers (or their
                        // underlying IComparables, etc) that are bogus.
                        try
                        {
                            Heapsort(left, right);
                            return;
                        }
                        catch (IndexOutOfRangeException)
                        {
                            throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
                        }
                        catch (Exception e)
                        {
                            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                        }
                    }

                    int i = left;
                    int j = right;

                    // pre-sort the low, middle (pivot), and high values in place.
                    // this improves performance in the face of already sorted data, or 
                    // data that is made up of multiple sorted runs appended together.
                    int middle = GetMedian(i, j);

                    // Add a try block here to detect IComparers (or their
                    // underlying IComparables, etc) that are bogus.
                    try
                    {
                        SwapIfGreaterWithItems(i, middle); // swap the low with the mid point
                        SwapIfGreaterWithItems(i, j);      // swap the low with the high
                        SwapIfGreaterWithItems(middle, j); // swap the middle with the high
                    }
                    catch (Exception e)
                    {
                        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                    }
                    Object x = keys[middle];
                    do
                    {
                        // Add a try block here to detect IComparers (or their
                        // underlying IComparables, etc) that are bogus.
                        try
                        {
                            while (comparer.Compare(keys[i], x) < 0) i++;
                            while (comparer.Compare(x, keys[j]) < 0) j--;
                        }
                        catch (IndexOutOfRangeException)
                        {
                            throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
                        }
                        catch (Exception e)
                        {
                            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                        }
                        Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
                        if (i > j) break;
                        if (i < j)
                        {
                            Object key = keys[i];
                            keys[i] = keys[j];
                            keys[j] = key;
                            if (items != null)
                            {
                                Object item = items[i];
                                items[i] = items[j];
                                items[j] = item;
                            }
                        }
                        i++;
                        j--;
                    } while (i <= j);

                    // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
                    // following calls recrusively sort the smaller half.  So we subtrack one from depthLimit here so
                    // both sorts see the new value.
                    depthLimit--;

                    if (j - left <= right - i)
                    {
                        if (left < j) DepthLimitedQuickSort(left, j, depthLimit);
                        left = i;
                    }
                    else
                    {
                        if (i < right) DepthLimitedQuickSort(i, right, depthLimit);
                        right = j;
                    }
                } while (left < right);
            }

我们可以看到使用的排序方法是用的快排,所以它的时间复杂度为O(nlogn)

总结

在分析完之后,我们可以知道List的效率并不高,只是通用性强,方便而已,大部分的算法都是使用线性复杂度的算法,这种算法遇到规模比较大的计算量级的时候就会照成大量的CPU的消耗。而且它的内存分配方式极其的不合理,只要元素不断的增加就会多次new数组,然后抛弃原来的数组,造成GC压力。所以List是一个好用但不高效的组件。

[算法]归并排序

概念

使用的思想是分治思想。把需要排序的数组中重建分成两部分,然后前后两部分分别排序,需要一直分解下去,直到能两个值相互比较。然后再将排序好的两个部分合并在一起。

合并

我们需要申请一个临时数组,这个数组的大小和我们排序的两个组的大小之和一样。然后我们用两个下标i,j,来标识我们当前读到的是两个组的第几个位置,然后这两个下标的值来做比较,但一个值满足要求的时候,我们就把这个值放在临时数组里,然后这个下标后移一位,继续比较。当任意一个下标到达那个组的最后一位的时候,我们就不需要做比较了,直接把另外一组剩下的放在临时数组的最后。

void merge_sort_c(int [] a,int p,int r)
            {
                if (p >= r)
                    return;
                int q = (p + r) / 2;
                merge_sort_c(a,p, q);
                merge_sort_c(a, q + 1, r);
                merage(a, p, q, r);
            }
            void merage(int[]a,int p,int q,int r)
            {
                int i = p;
                int j = q+1;
                int k = 0;
                int[] temp = new int[r - p+1];
                while (i <= q && j <= r)
                {
                    if (a[i] <= a[j])
                    {
                        temp[k++] = a[i++];
                    }
                    else
                    {
                        temp[k++] = a[j++];
                    }
                }
                int start = i;
                int end = q;
                if (j <= r)
                {
                    start = j;
                    end = r;
                }
                while (start <= end)
                {
                    temp[k++] = a[start++];
                }
                for(int ii = 0; ii < r - p+1; ii++)
                {
                    a[p + ii] = temp[ii];
                }
            }
  1. 当我们把第二组的多出来的数据整体放在第一组后面,那归并排序是稳定排序

  2. 归并排序的时间复杂度o(nlogn)

  3. 归并排序的空间复杂度不是原地排序,因为在合并的时候需要临时空间。o(n)

[算法]选择排序

概念

也分为未排序区和排序区。但是选择排序每次都从未排序中找到我们要的元素放在排序区的最后。

int[] t = new int[10] { 43, 23, 432, 5, 2, 6, 43, 2, 67, 4 };
                for(int i = 0; i < t.Length; i++)
                {
                    int v = t[i];
                    int index = i;
                    for (int j = t.Length-1; j > i; --j)
                    {
                        if (v > t[j])
                        {
                            index = j;
                            v = t[j];
                        }
                    }
                    t[index] = t[i];
                    t[i] = v;
                }
                for(int i = 0; i < t.Length; i++)
                {
                    Console.WriteLine("{0}={1}", i, t[i]);
                }
  1. 因为只会交换一次我们找到满足条件的数据放在已排序的最后,所以这个排序的空间复杂度为o(1),是原地排序算法

  2. 这个排序不是稳定排序算法,因为每次都会去找剩下满足的元素和前面的元素进行交换

  3. 最坏,最好,和平均时间复杂度都是o(n*n).

[算法]插入排序

概念

插入排序就是把数组分为两个区间,一个是有序区间,一个是未排序区间。初始的时候有序区间就只有一个元素,那就是数组的第一个元素,然后取未排序区间中的元素往有序区间中插进去,一直等到未排序区间中的所有元素为空。

int[] t = new int[10] { 54, 23, 43, 2, 3, 5, 1, 2, 6, 7 };
                for (int i = 0; i < t.Length; i++)
                {
                    int v = t[i];
                    int j = i - 1;
                    for (; j > 0; --j)
                    {
                        if (v > t[j])
                        {
                            t[j + 1] = t[j];
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                for(int i = 0; i < t.Length; i++)
                {
                    Console.WriteLine("{0}={1}", i, t[i]);
                }
  1. 插入排序算法不需要额外的空间,所以它的空间复杂度为o(1),是原地排序算法。

  2. 插入的时候只是插到它所需要的位置,不会修改它后面位置的顺序,所以是稳定排序算法。

  3. 最好情况下,我们要排序的数据是有序的,所以我们只需要做o(n)的时间复杂度。最坏的情况下,我们要排序的数据是逆序的,所以我们要做o(nn)的时间复杂度。在数组中插入一个数据的时间平均时间复杂度是o(n),我们需要执行n次操作,所以平均时间复杂度是o(nn)。

[算法]冒泡排序

概念

每次冒泡就是相邻的两个数进行比较,如果两个数据的关系不满足我们所要求的的,那我们就进行交换。一次冒泡操作至少会让一个元素移动到它所应该在的位置。

int[] t = new int[10] { 2, 3, 4, 2, 43, 54, 23, 43, 1, 67};
for(int i = 0; i < t.Length; i++)
    {
      for(int j = 0; j < t.Length-i-1; j++)
          {
              if (t[j+1] > t[j])
                 {
                   int temp = t[j+1];
                   t[j+1] = t[j];
                   t[j] = temp;
                  }
            }
     }
     for(int i = 0; i < t.Length; i++)
        {
          Console.WriteLine("{0}={1}", i, t[i]);
        }
  1. 因为只涉及到相邻的两个数的操作,所以它的空间复杂度是o(1)是原地算法排序。

  2. 因为只有当相邻的两个元素不一致的时候我们才会去交换两个元素的位置,所以这个排序也是一个稳定排序算法。

  3. 在最好的情况下就是说他们已经是有序的情况下他们的时间复杂度是o(n),在最坏的情况下就是说它们是反倒序的情况下,它的时间复杂度是o(nn);还有一种叫平均时间复杂度n(n-1)/4,一般来说我们就看做o(n*n)。

[图形学]Unity Sharder入门精要(一)

前言

这一片文章写的是关于Unity Sharder入门精要第二章的读书笔记。

知识点

流水线

就是把一整套大步骤分为多个小步骤,然后可以一起执行。

渲染流水线

就是把三维场景中的内容渲染成一张二维图像。由CPU和GPU共同完成的。
这分为三个阶段:应用阶段,几何阶段,光栅化阶段

应用阶段:

这个阶段是由我们应用程序所主导的,因此通常由CPU负责实现。所以在这个阶段,我们开发者是有绝对的控制权。
三个主要任务:

  1. 准备场景数据
  2. 粗粒度的剔除工作
  3. 设置渲染状态
    场景数据:包括但不限于:摄像机位置,摄像机的视椎体,场景中的模型,光源
    粗粒度剔除工作:把那些完全不可见的物体剔除出去,这样就不需要再发给几何阶段出来,减少GPU工作。
    渲染状态设置:包括但不限制于:模型使用的材质,使用的纹理,使用的shader。
    在这个阶段重要的输出是渲染图元也就是渲染所需要的几何信息。这些图元被传递到下一个阶段-几何阶段
    三个阶段
  4. 把数据加载到显存中。
  5. 设置渲染状态
  6. 调用Draw Call
    把数据加载到显存中:渲染所有的数据都需要从硬盘加载到系统内存中,然后再把网格和纹理等数据又被加载到显存中。因为显卡对于显存的访问速度更快, 数据被加载好了以后,这些数据就可以被移除了,但是如果我们还需要做一些cpu的检测,那可以暂时不移除。
    设置渲染状态:渲染状态就是用来定义网格是被怎样渲染出来的,比如用了哪个定点着色器,用了什么光源属性,用了什么材质等等,如果我们没有更改渲染状态,那么所有的网格都讲使用同一种方法来进行渲染。
    调用Draw Call:Draw Call就是一个命令,从cpu发送到GPU,用来告诉GPU渲染哪个图元,这里面不包含任何材质信息,因为我们在前几步就已经把数据加载到了显存中了。当我们调用了Draw Call以后,GPU就会根据设置的渲染状态,和定点数据来进行计算,输出需要显示的像素。

    几何阶段

    这个阶段主要用于处理所有和我们要绘制的几何相关的事情,把从应用阶段保存到显存中的图元,在收到Draw Call指定的图元后,进行逐顶点,逐多边形的操作,在这个阶段有个最重要的任务就是把顶点坐标变换到屏幕空间中,然后再把这个坐标交到光栅器进行最后的处理。
    五个关键步骤

  7. 顶点着色器处理
  8. 曲面细分着色器处理
  9. 几何着色器处理
  10. 裁剪
  11. 屏幕映射处理
    顶点着色器
    这步是完全可编程的。当Draw Call通知需要被处理的图元时,这里就开始这一步,把图元的顶点进行变化,和着色。在这步我们是不能创建和销毁任何一个顶点,并且不能得到顶点和顶点间的关系,但是就是因为这样的相互独立性,所有我们可以利用GPU的特性进行并行化处理每一个顶点,这就意味着,处理顶点的速度将会变得很快。
    坐标转换:
    顶点着色器在这步改变顶点的位置,这个在顶点动画中是个非常有用的。需要注意的一点是,无论我们在顶点着色器中怎么改变顶点的位置,我们都需要把顶点坐标从模型空间转换到齐次剪裁空间,然后再得到归一化的设备坐标。
    曲面细分着色器
    这是一个可选的着色器,用于细分图元。
    几何着色器
    这也是一个可选着色器,可以被用来执行逐图元的着色操作,或者被用于产生更多的图元。
    裁剪
    用于裁剪那些不在摄像机视野方位内的顶点,并且剔除某些三角图元的面片,这一步是可配置的。一些图元的点有一部分在摄像机的视野外面,这个时候,我们就需要把摄像机视野外的点个裁剪掉,在和裁剪接触面来新建几个点,用来替换视野外的点。
    屏幕映射
    这一步是不可编程,也不可以配置的。这步负责把每个图元的坐标转换到屏幕坐标系中。这一步输入进来的坐标其实还是一个三维坐标,而我们的屏幕坐标系是一个二维坐标,所以我们要把图元显示出来,就得在这步来进行一次坐标转换,把三维坐标映射到屏幕坐标中,因为屏幕的坐标和屏幕的分辨率有很大的关系,所以这里将会进行一次矩阵计算。这步计算得到了顶点对应屏幕上的哪些像素以及距离这个像素有多远。这步只处理图元坐标中的x,y,对于z我们将保留原始值。只包含x,y的叫屏幕坐标系,加上一个z就是窗口坐标系。

    光栅化阶段

    把上一个阶段传递过来的数据产生屏幕上的像素,并渲染出最终的图案。主要的任务就是决定每个渲染图元中的哪些像素应该被绘制在屏幕上。它需要对上一个阶段得到的逐顶点数据进行插值,然后再进行逐像素处理。
    四个步骤

  12. 三角形设置
  13. 三角形遍历
  14. 片元着色器
  15. 逐片元操作
    三角形设置
    这个阶段计算光栅化一个三角网格所需要的所有信息。从上一个阶段输入进来的是三角网格的顶点,但是当我们要计算这个三角形所覆盖的像素情况时候,我们就需要计算每个边所对应的像素坐标。所以这步的最主要的功能就是为了能输出下一阶段所需要的三角网格的数据。
    三角形遍历
    这个阶段将会检查每个像素是否被一个三角网格所覆盖,如果被这个像素被覆盖了,那就生成一个片元,这样找到所有被三角网格所覆盖的过程就叫做三角形遍历(扫描变换)。使用三角网格3个顶点的顶点信息对整个覆盖区域的像素进行插值。这样输出的就是一个片元序列。这个片元不是真正意义上的像素,这里面包含了很多状态,这些状态就是用于计算像素最终颜色的。
    片元着色器
    这是一个很重要的可编程着色器阶段。其中很重要的一个技术就是:纹理采样。为了方便在这个阶段进行纹理采样,我们在顶点着色器阶段输出了每个顶点对应的纹理坐标。然后经过对三角网格的三个顶点对应的纹理坐标进行插值以后,就可以得到覆盖在片元上的纹理坐标。这步虽然可以完成很多重要的效果,但是它只能影响到一个片元,在这步里是不可以将自己的任何结果发送给其他片元。但是有个例外就是可以访问导数信息。
    逐片元操作
    这一阶段的主要目的就是合并。这一步也是一个高度可配置性。
    两个重要任务
  16. 决定每个片元的可见性
  17. 进行颜色合并
    在做片元可见性时候,我们需要对片元做一系列的测试。只有通过了所有的测试才可以进行颜色合并。如果没有通过测试,那么这个片元在前面所有的处理都是白费的,因为这个片元会被舍弃掉。有两个最基本的测试-深度测试和模板测试。
    模板测试
    模板测试相关的就是模板缓冲。开启以后,GPU会首先读取模板缓冲区中该片元位置的模板值,然后将该值和读取到的参考值进行比较。这个比较函数可以由开发者指定。如果片元没有通过就会被舍弃。不管片元有没有通过模板测试,我们都可以根据模板测试和下面的深度测试结果来修改模板缓冲区,这个操作也是由开发者决定的。
    深度测试
    如果开启了深度测试,那么gpu会把该片元的深度值和已经存在于深度缓冲区中的深度值进行比较。这个比较函数也是开发者可以设置的。如果没有测试通过,那么这个片元就会被舍去。这里有个地方和模板测试不一样的,就是如果没有通过测试那么这个片元就没有权利更改深度缓冲区中的值。如果通过了测试还可以通过开启/关闭深度写入来决定是否要用到这个片元的深度值覆盖掉原有的深度值。
    合并
    我们所讨论的渲染过程是一个物体接着一个物体画到屏幕上的。而每个像素的颜色信息被存储在一个名为颜色缓冲的地方。因此,当我们片元通过了所有测试将要被渲染出来的时候,颜色缓冲区中往往会有上一次渲染后的颜色结果,那么我们这次的片元的颜色将要怎么渲染呢?是覆盖还是其他处理,这里就需要的用合并来解决了。当如果是不透明的物体,我们就可以关闭混合,这样颜色值就会覆盖掉颜色缓冲区中的颜色。但是对于半透明的物体,我们就需要使用混合来让这个物体看起来是透明的,gpu会取出原颜色和目标颜色,将两种颜色进行混合,原颜色是从片元着色器中取出来的颜色值,目标颜色是存在与颜色缓冲区中的颜色值,之后使用一个混合函数来进行混合操作。这个混合函数通常跟透明通道息息相关。
    为了避免我们看到那些正在进行光栅化的图元,GPU会使用双重缓冲的策略。对于场景的渲染是在幕后发生的,就是后置缓冲。当场景已经被全部渲染到后置缓冲中,GPU就会交换后置缓冲区和前置缓冲区的内容。前置缓冲区就是我们所看到的图像。

    优化知识点

    一般在谈到优化,我们基本上都会考虑优化Draw Call这个属性,但是在我们这章的内容上,我们了解到Draw Call只是一个命令集,但是为什么我们要优化Draw Call的数量呢?这里我们需要考虑在发送Draw Call的之前CPU还做了什么操作,一个是加载数据,一个是设置渲染状态,加载数据的话,有人说是通用在内存上的交互,因为在Unity中我们读取AB包的时候,数据以及在内存上了,然后再从内存加载到显存上,但是在操作系统层面上,内存和显存的块都是在一个地方的,所以这步加载是没有什么消耗的。那最大的消耗就是在设置渲染状态了,看了下Unity官方的文档,Draw Call是资源密集型操作,主要开销是Draw Call之间的状态变化(列如切换到不同材质),而这种情况会导致图形驱动程序中执行密集型验证和转换步骤。所以我们减少的Draw Call的数量就是为了减少cpu上的消耗,导致卡顿。

[读书笔记]具体数学1.1

知识点

  1. 稍加推广:先研究一个问题小的情况,通过尝试得到小问题的答案,然后思考大范围的问题

  2. 命名并求解:把大范围的问题具体化,设置一个变量名然后去解这个变量名的答案

  3. 递归式:给出一个边界值,以及一个用前面的值给出一般值的方程。

  4. 数学归纳法:证明某个命题对所有满足n \geq n_{0}的整数n都成立的一般方法。
    首先我们在n取最小值n_{0}时证明该命题,这一步骤称为基础;然后对
    n > n_{0}
    假设该命题对n_{0}与n-1之间(包含它们在内)的所有值都已经被证明,再证明该命题
    对n成立,这一步骤称为归纳。这样一种证明方法仅用有限步就得到无限多个结果。

  5. 实际证明使用三个阶段:
    (1) 研究小的情形,有助于我们洞察该问题
    (2)对有意义的量求出数学表达式并给出证明
    (3)对表达式求出封闭形式并给出证明
    递归式->递归解

[读书笔记]算法导论2.1

知识点

  1. 循环不变式
    需要证明个性质:

    1. 初始化:循环的第一次迭代之前,它为真。
    2. 保持:如果循环的末次迭代之前它为真,那么下次迭代之前它仍为真
    3. 终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法的正确性。

习题

1.1

31,41,59,26,41,58
31,41,59,26,41,58
31415926,41,58
26,31,41,5941,58
26,31,41,41,5958
26,31,41,41,58,59
1.2

INSERTION-STOP(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

1-3

LINEARSEARCH-STOP(A,u)
    for i = 1 to A.length
        key = A[i]
        if key == u 
            return i
    return nil

1-4

形式化描述:对于二进制的相加,是低位数相加,为2进一位,当前位为当前位-2,进的一位参加下一位的相加。

BINARYADD-STOP(A,B)
    C[1] = 0
    for i = 1 to n
        keyc = C[i]
        keya = A[i]
        keyb = B[i]
        sum = keyc + keya + keyb
        if sum > 1 
            C[i+1] =1
            C[i] = sum - 2
        else
            C[i+1] = 0
            C[i] = sum
    return C