none
鼠标和区域判断的问题 RRS feed

  • 问题

  • 微软是如何让windows系统快速判断出鼠标指针当前在哪个窗口的呢,以便将鼠标消息发送到这个窗口?
    试想一下现在让你实现图形界面的这部分功能,你怎么去实现呢?
    能获得的数据只有屏幕大小,各个窗口的可见区域,以及鼠标的坐标。鼠标消息从硬件获得,在系统消息队列中排了长长的队伍,等待着你把它们取出来然后放到正确的窗口的消息队列中。而你能获得的数据仅仅是鼠标的坐标和你自己维护的一堆窗口可见区域数据,你该如何快速找到鼠标当前处在哪个窗口区域呢?肯定不能用遍历所有窗口可见区域的办法,这是最笨的办法,难道鼠标每移动一个像素就要遍历一边,否则万一这一个像素的变化正好使它从一个窗口到了另一个窗口怎么办?更何况极端地说如果有十万个窗口,难道也要从头遍历?
    我真的想不出能有什么好的算法解决这个问题。个人考虑了个方法,可能贻笑大方:创建一个二维数组,行和列正好对应屏幕的横纵像素值,数组元素就是指向窗口对象的指针,根据窗口的可见区域给每个数组元素赋值,窗口位置改变了或者可见区域改变了就更新数组相应元素的值,这样只要知道鼠标横纵坐标就能直接获得窗口对象,并把消息发给它。
    这个方法总感觉别扭,在此抛砖引玉,真不知道正确的方法是什么!
    LHL
    • 已编辑 lhlzhxh 2009年8月20日 7:44
    2009年8月20日 7:38

答案

  • 可以考虑采用某些算法加快窗口查找.
    但一般来说,GUI还是采用树遍历的方法.
    而且,GUI树基本不会出现某个节点有数以万计的子节点的情况.
    可以使用spy++查看windows的窗口树,桌面窗口的子节点,既顶层窗口,一般维持在十几个到几十个之间,再下层的子窗口会更少.而且层次一般控制在2到5层之间.
    在正常情况下,进行一次窗口查找,只需要进行几十次区域匹配.
    这样的计算量,按windows的鼠标消息采集间隔来说,基本可以忽略.

    • 已标记为答案 lhlzhxh 2009年8月24日 8:42
    2009年8月21日 1:00

全部回复

  • 1. windows 的窗口组织不是平板结构,而是一棵树.
    树的根节点是桌面窗口,覆盖了整个屏幕.桌面窗口下是各顶层窗口,再下面是各子窗口.
    暂时可以假定,所有子窗口的可见区域都在它父窗口的可见区域内.
    按照窗口树结构,根据当前鼠标位置一层层往下找,每一层逐一排除未指向的窗口,从而可以全部排除它的子窗口.
    这样下来,效率不会很慢,对于现在的CPU,完全可以接受.
    2. windows 鼠标消息的采集有一定的时间间隔,基本不会出现每个像素采集一次的情况.
    2009年8月20日 8:47
  • 如果需要低延迟采集应该使用HOOK
    麻烦把正确答案设为解答。
    2009年8月20日 8:49
    版主
  • 确实是个树,还是个多叉树,这样的话,一般来说一个树节点应包含子节点的链表。
    那就意味着首先要遍历根节点的子节点链表,然后找到一个鼠标指针在其范围内的顶层窗口,然后再遍历这个窗口的子节点链表,再找到一个鼠标指针在其上的窗口,最终找到一个叶子节点为止,或者找到一个节点,它的叶子节点都不在指针之下。
    这样的话,如果我真要疯狂创建数以万计的可见窗口,不管是顶层窗口也好还是子窗口也好,反正就是处于同一父窗口下的窗口,那么,且不管其他资源的消耗,如果我不停移动鼠标的话是不是还真能看出CPU占用明显上涨呢?
    难道真的就是通过遍历的方式查找?
    另外,刚才之所以把窗口放到一个平面上考虑,是因为觉得对于鼠标来说,窗口就是平面的。窗口虽然有层叠关系,但是对于鼠标来说它只管窗口的可见区域,而不是窗口的窗口区域或者说实际形状。所有窗口的可见区域拼起来正好是一个整屏。我当时感觉只考虑可见区域可能能直接排除很多不可见窗口的干扰,能减少比较。这个问题我考虑了一段时间,想不出答案,哈哈。
    之所以想这个问题是因为最近想学习用Dx3D做图形界面,如果要自己模拟窗口的功能,可能要需要解决这个问题。


    LHL
    2009年8月20日 9:33
  • 可以考虑采用某些算法加快窗口查找.
    但一般来说,GUI还是采用树遍历的方法.
    而且,GUI树基本不会出现某个节点有数以万计的子节点的情况.
    可以使用spy++查看windows的窗口树,桌面窗口的子节点,既顶层窗口,一般维持在十几个到几十个之间,再下层的子窗口会更少.而且层次一般控制在2到5层之间.
    在正常情况下,进行一次窗口查找,只需要进行几十次区域匹配.
    这样的计算量,按windows的鼠标消息采集间隔来说,基本可以忽略.

    • 已标记为答案 lhlzhxh 2009年8月24日 8:42
    2009年8月21日 1:00