[讨论]如果M$只给了我们SetPixel要怎么办……[挑战]希望各位高手踊跃参加！

Question

假设M$的API库是为了节省空间而设计的，那么其中有可能只有SetPixel这一个画图函数
那么我们要如何画出线段、曲线、圆、椭圆，如何填充区域，如何……为了提高我们VB程序员的水平，为了知识共享，在此有请各位大侠，给出模仿现有API实现以下功能的、只使用SetPixel函数的源码：
1、画线段(LineTo)
2、画圆和椭圆(Ellipse)
3、画贝塞尔曲线(PolyBezier、PolyBezierTo)
4、画\填充多边形(Polygon、Polyline、PolylineTo)
5、填充不定区域(FloodFill)
每一项函数中效率最佳、功能最灵活的代码将获得本人给出的200分奖励（单独开贴），希望各位高手踊跃参加！希望斑竹能够置顶，这是一件有利于全体VB程序员的好事。

Answer 1

填充任意多边形的算法我可以做到，而且比起传统的“种子填充算法“效率提高了很多详细的说明参见：http://www.dev-club.com/club/bbs/showAnnounce.asp?page=1&id=2144469

Answer 2

去学《计算机图形学》
我最近在写一个DOS下的图形界面库
用到了SVGA，所以准备自己写代码模拟gdi32.dll
所以VB版没有时间写

Answer 3

M$的API库是为了保持设备无关性
画线、画椭圆……有硬件实现的（如打印机）

Answer 4

你说的就是Win CE的环境了，里面啥都没有，作图全得从最底层做起，不过这些《计算机图形学》上全有现成的源代码啊，而且效率也不错了

Answer 5

电子工业出版社的计算机图形学么？上面的代码的确有用，可是……
比如画线的代码无法控制宽度，填充区域的代码效率并不高……所以才来这里发贴的我倒不是想在WinCE环境下编程，而是希望用VB写出可以用图形的真正绿色软件（使用极少的API），甚至我正在研究如何越过Windows的API将数据放到设备中……虽然听起来很没有希望

Answer 6

学习！以前未曾考虑过效率，不过我感觉VB中的画图比C中的更好用。

Answer 7

有没写过DOS程序
为了提高效率，连画点函数都要自己写（直接写屏）

Answer 8

我现在就在为SVGA的画点函数伤脑筋
由于DOS只能以16位寻址，所以画到某个地方时需要换（内存）页，而SVGA规定可以使用非标准内存页大小
同时SVGA支持4、8、15、16、24五种格式显示模式。特别是24位是奇数地址，不能被2的倍数整除，所以在写某页最后一个像素的时候要逐Byte判断是否需要换页。这样影响效率。所以写一个高效的画点函数是很麻烦的

Answer 9

画点是图形编程的基础中的基础，不可等闲
记得以前在dos下tc写图形程序，开始时是13h写屏
然后是vesa的4015h、modex、xms，再然后就是大家熟悉的dos4gw啦，哈哈
还真的是非常怀念啊！

Answer 10

to agua06(阿瓜):
你的算法我研究过了，不过那个算法应该属于“5、填充不定区域(FloodFill)”
如果8月15日前没有看到比你的算法更好的算法，我就给分了

Answer 11

那样子，，呵呵，，，
不出一年就会有人（企业）做掉MS，接着取而代之，给我们足够用的API函数库所以诸位不用担心

Answer 12

有一本
《最新 VESA SVGA 图形图像编程秘笈》 （到现在不知道还新不新了，反正我买了好几年）
李军写的，北京航空航天大学出版社。里面有这类方法。是Dos下用TC 3.0写真彩程序的书，还有使用XMS等等值得参考的代码。
为了效率使用了大量汇编。从画点、画线，矩形，圆一直到动画都有代码。不过图形模式初始化部分的代码书上没写全（为的是让你另外购买标价￥150的磁盘）
有兴趣的不妨看看。

Answer 13

to Ringfo(狂生A-9):
好没有危机感啊……我们应该做一个API库，然后来卖钱to Garfield(猫仔|别忘了结帖,同志):
这本书我有，但是其中东西实在有很多缺憾啊……所以才来这里请教的

Answer 14

我想知道PC里面，CPU和显卡，到底那一个主管画图，怎样分工，windows的GUI是哪一个画的……

Answer 15

to Silenker():
CPU和显卡都要管画图，具体分工请找书来看吧。
GUI是CPU画的，但是多数都使用了显卡的加速

Answer 16

新的显卡不都有个叫做GPU的吗？据说绘图大多数都用GPU完成了

Answer 17

to jlum99(闲人):
所谓GPU的绘图几乎完全是指在3D模式下的绘图
当然有大部分2D效果是GPU参与绘制的，但在此时起主要作用的还是CPU

Answer 18

直接用DirectX不就得了，劳什么神啊

Answer 19

to ffb(我编):
照这么说的话DX是怎么来的？你不想知道么？

Answer 20

用中学学过的函数
直线用：一次函数 两点式
多边形用一次函数两点式，的分段函数
圆用x^2+y^2=r^2
椭圆x^2/a^2+y^2/b^2=c^2
填充：
需要设一个点，扫描图片的所有点
把点代入函数，如果左边大于右边，就不画点，反之画点

Answer 21

你那个api是什么呀
能不能告诉我具体声明
发到我邮箱里，我编好了给你发回去，现在我有点忙
不好意思

Answer 22

忘了告诉你邮箱了：
[email protected]

Answer 23

to DIPDERK(泥巴):
画圆、椭圆谁都会，但是要保证可控与高效，就难了。像API中的画椭圆函数，可控性很强，而且性能也很好，那我们应该如何做同时具备这两点性能的函数呢？
还有API的声明：
Public Declare Function SetPixel Lib "gdi32" Alias "SetPixel" (ByVal hdc As Long, ByVal x As Long, ByVal y As Long, ByVal crColor As Long) As Long
Public Declare Function LineTo Lib "gdi32" Alias "LineTo" (ByVal hdc As Long, ByVal x As Long, ByVal y As Long) As Long
Public Declare Function Ellipse Lib "gdi32" Alias "Ellipse" (ByVal hdc As Long, ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long) As Long
Public Declare Function PolyBezier Lib "gdi32" Alias "PolyBezier" (ByVal hdc As Long, lppt As POINTAPI, ByVal cPoints As Long) As Long
Public Declare Function PolyBezierTo Lib "gdi32" Alias "PolyBezierTo" (ByVal hdc As Long, lppt As POINTAPI, ByVal cCount As Long) As Long
Public Declare Function Polygon Lib "gdi32" Alias "Polygon" (ByVal hdc As Long, lpPoint As POINTAPI, ByVal nCount As Long) As Long
Public Declare Function Polyline Lib "gdi32" Alias "Polyline" (ByVal hdc As Long, lpPoint As POINTAPI, ByVal nCount As Long) As Long
Public Declare Function PolylineTo Lib "gdi32" Alias "PolylineTo" (ByVal hdc As Long, lppt As POINTAPI, ByVal cCount As Long) As Long
Public Declare Function FloodFill Lib "gdi32" Alias "FloodFill" (ByVal hdc As Long, ByVal x As Long, ByVal y As Long, ByVal crColor As Long) As Long

Answer 24

不我要得不是这些
我要的是你那个效率高的API
就是只有“setpixel”的那个。
用setpixel当然慢了
我记得以前有一个帖子介绍过快速画点的api，是stepixel的几十倍
因为setpixel中有大量的功能不是用做图象处理的
所以stepixel虽然画点，lineto虽然画许多点，但是速度都差不多。并不是因为算法好
而是因为用setpixel画线，会重复工作
所以要一个效率高的函数自己编

Answer 25

对了就是这个，置顶帖子
 用VB写高效的图像处理程序 1.0β
http://www.fantasiasoft.net/Zyl910/VBImgOp.htm

Answer 26

to DIPDERK(泥巴):
如果是这样请你做实验：
1）使用Lineto，画某一线段，测试速度
2）使用lineto，画同一险段，但使用两倍于原来的宽度，再测试速度
3）我们应该认为，DIB画图法（姑且让我这么称呼）所用的时间应该就是WindowsAPI内部画图“真正”使用的时间（因为DIB_Ptr的方法在VB6中效率反而较低），假设这个时间占API画图法使用时间的x%，那么画两倍宽度的线段应该使用的时间会多出相对应画原宽度线段使用时间的x%，但是你应该可以看到，这个时间明显大大的少于这个预期的值。
另外，这个帖子并不准备考虑画图方法本身的效率问题，我们应该尽量考虑算法的效率和灵活程度。

Answer 27

希望用VB写出可以用图形的真正绿色软件（使用极少的API），===================================================
呵呵，这种说法太可笑了。
API是系统基层接口。你的软件是否绿色，跟你使用多少API毫无关系。

Answer 28

to icansaymyabc(学习与进步):
非常抱歉，我在写这个帖子的时候没有注意到这个错误，现在又不知道怎么改，正好仁兄提出来了，我就在此解释一下，应该把这句改成：希望通过VB学会写脱离平台的图形图像应用软件

Answer 29

原来在DOS下写过，在WINDOWS下计算机升级那么快，没考虑过了。

Answer 30

觉得无论如何VB都要带个dll真是没办法，再怎么样也头痛,VB本身速度又慢,不如大包小包的好，要不还是用C算了

Answer 31

windows屏幕保护程序有一个叫塞尔曲线

Answer 32

setpixel是基于gdi的
如果M$只给了我们SetPixel要怎么办，那么我们要搞清楚setpixel是怎样工作的，然后去掉要包装的指令

Answer 33

to subzero(赘姆烂壳):
SetPixel的工作原理很简单（我说的是原理！），所以不做讨论。暂时我们只讨论在原理上具有一定复杂性的一些API。

Answer 34

ft...在DOS时代我们是怎么做的呢？有什么函数啊？但是那些图线怎么画呢？看看计算机图形学吧。所有的基本图形都有算法对应。

Answer 35

to : nik_Amis(Azrael)
用第归 计算 闭合图形围成的 面积与周长比最大
(周长不是 简单的点的个数,要分成两类
 一,旁边有这样的 点(这个点与旁边的点的横坐标或纵坐标相同) 这样的点长度为1
 二,旁边没有这样的点 这样的点长度为1.414)可以先画1/8圆 然后再对原点进行加减运算从一个等腰直角三角形开始固定一条直角边(半径),和斜边
对另一条直角边上的点进行移动(从离斜边近的点开始)
将逐个点依次向圆心(固定直角边的锐角方向)移动(每次移动,有点像2进制的加减法
直到 面积/周长 最大为止(一定要计算这个"圆"的面积,不要计算1/4圆的面积 否则容易忽略直径上的点)
周长要计算的是最靠近圆心的点的长度这样不用乘除但是 要用到大量的条件语句
所以要用第归

Answer 36

To :agua06(阿瓜) &  CCL(VB卡尔) 
    在我看来，种子填充法和腐蚀填充法 的差距并没有看上去那么悬殊吧呵呵。
    那么原因在哪里呢？
    我看了一下午，其实是DoEvents搞的鬼。
    其实很容易想到：DoEvents要把结果表示出来是需要时间的。
    腐蚀填充法中，写了4个PSet才 有一个DoEvents
    而种子填充法，写了2个PSet就 有一个DoEvents
    这样种子填充法就把大量的时间花在DoEvents 上了
不信我们可以做个实验，去掉DoEvents

Answer 37

Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)
Private Type POINTAPI
      X As Long
      Y As Long
End Type
Private Const PS_SOLID& = 0Private Sub Pic2_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
Dim pixel() As POINTAPI
Dim strck() As POINTAPI
Dim pstrck As Long
Dim p As POINTAPIReDim pixel(Pic2.ScaleHeight * Pic2.ScaleWidth)
ReDim strck(Pic2.ScaleHeight * Pic2.ScaleWidth)pstrck = 1
strck(pstrck).X = X
strck(pstrck).Y = YPic2.PSet (X, Y), vbGreenDo While pstrck > 0  CopyMemory pixel(0), strck(0), Len(p) * (pstrck + 1)
  i = pstrck
  Debug.Print i
  pstrck = 0
  For j = i To 1 Step -1
     
     If Pic2.Point(pixel(j).X - 1, pixel(j).Y) = RGB(255, 255, 255) Then
        pstrck = pstrck + 1
        strck(pstrck).X = pixel(j).X - 1
        strck(pstrck).Y = pixel(j).Y
        Pic2.PSet (pixel(j).X - 1, pixel(j).Y), vbGreen
        
     End If
     
     If Pic2.Point(pixel(j).X + 1, pixel(j).Y) = RGB(255, 255, 255) Then
        pstrck = pstrck + 1
        strck(pstrck).X = pixel(j).X + 1
        strck(pstrck).Y = pixel(j).Y
        Pic2.PSet (pixel(j).X + 1, pixel(j).Y), vbGreen
        
     End If     If Pic2.Point(pixel(j).X, pixel(j).Y - 1) = RGB(255, 255, 255) Then
        pstrck = pstrck + 1
        strck(pstrck).X = pixel(j).X
        strck(pstrck).Y = pixel(j).Y - 1
        Pic2.PSet (pixel(j).X, pixel(j).Y - 1), vbGreen
        
     End If     If Pic2.Point(pixel(j).X, pixel(j).Y + 1) = RGB(255, 255, 255) Then
        pstrck = pstrck + 1
        strck(pstrck).X = pixel(j).X
        strck(pstrck).Y = pixel(j).Y + 1
        Pic2.PSet (pixel(j).X, pixel(j).Y + 1), vbGreen
        
     End If
  Next
  
  'DoEvents
  LoopMsgBox "ok"End Sub
-------------------------------------------------------------------------------
===============================================================================
Private Sub xy(a As Single, b As Single)
Dim m As Integer
If Pic3.Point(a, b) = RGB(255, 255, 255) Then
Pic3.PSet (a, b), vbGreen
'DoEvents
xy a + 2, b + 2
xy a - 2, b + 2
xy a - 2, b - 2
xy a + 2, b - 2
Else
Exit Sub
End If
End Sub
Private Sub Pic3_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
xy X, Y
xy X + 1, Y
xy X, Y + 1
xy X + 1, Y + 1
xy X + 2, Y
xy X + 3, Y
xy X + 2, Y + 1
xy X + 3, Y + 1
End Sub
下面的xy子程序 是我用第归编的种子，在没有DoEvents的前提下和 腐蚀填充法速度差不多
由于怕超越堆栈的容量才分成8部完成。

Answer 38

To DIPDERK(泥巴):
你说的问题我也有注意到，但是我自己在.Net下写了个图形模块，由于是指令刷新的，所以没有DoEvents的干扰。测试结果是2^16边长的正方形“腐蚀填充法”用了不到“种子填充法”2/3的时间。但我对“种子填充法”作了一下研究发现，可能是该算法会重复画点（我自己做了个与图片对应的计数器，发现有最多画过3次的点）导致性能较低。
至于为什么常见的是“种子填充法”，我想可能还是有原因的，不知道谁能告知一下。

Answer 39

我好低估了doevents
呵呵
看看这几条语句：
For j = i To 1 Step -1
     
     If Pic2.Point(pixel(j).X - 1, pixel(j).Y) = RGB(255, 255, 255) Then
        pstrck = pstrck + 1
        strck(pstrck).X = pixel(j).X - 1
        strck(pstrck).Y = pixel(j).Y
        Pic2.PSet (pixel(j).X - 1, pixel(j).Y), vbGreen
        
     End If
。。
。。
。。
doevents
。。
如果把第一行设置为 断点，每次检测i的值就不难发现
第一次i=1，第二4，第三8，第四12……依次类推
画了这么多点才doevents，难怪我怎么编，在doevents
的条件下也赶不上了。其实他的腐蚀填充法也有检测以前的点，只是比种子填充法少。
所以我对其做了优化，不再通过检测屏幕的颜色来检测以前的点
以下为！！没有重复画点的！！腐蚀填充的优化代码：
Private Type POINTAPI
      X As Single
      Y As Single
End Type
Dim p(0 To 1000000) As POINTAPI
Dim Ma(1000, 1000) As Boolean
Dim j As Long
Dim k As Long
Dim l As LongPrivate Sub Picture1_MouseUp(Button As Integer, Shift As Integer, X As Single, Y As Single)
Dim a As Single
Dim b As Single
a = X: b = Y
Do
l = l + 1If l = 4 Then l = 0 ':DoEvents
If k = 0 Then p(0).X = a: p(0).Y = b
If Pic3.Point(p(k).X + 1, p(k).Y) = vbWhite And Not (Ma(p(k).X + 1, p(k).Y)) Then
j = j + 1
p(j).X = p(k).X + 1
p(j).Y = p(k).Y
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(p(k).X, p(k).Y + 1) = vbWhite And Not (Ma(p(k).X, p(k).Y + 1)) Then
j = j + 1
p(j).X = p(k).X
p(j).Y = p(k).Y + 1
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(p(k).X - 1, p(k).Y) = vbWhite And Not (Ma(p(k).X - 1, p(k).Y)) Then
j = j + 1
p(j).X = p(k).X - 1
p(j).Y = p(k).Y
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(p(k).X, p(k).Y - 1) = vbWhite And Not (Ma(p(k).X, p(k).Y - 1)) Then
j = j + 1
p(j).X = p(k).X
p(j).Y = p(k).Y - 1
Ma(p(j).X, p(j).Y) = True
End IfPic3.PSet (p(k).X, p(k).Y)
If k = j Then
Exit Do
End If
k = k + 1
Loop
End Sub。
这种腐蚀填充同样可以用第归来完成，但是由于需要内存太大，经常跃界
以下为第归子程序：
Private Sub Seed(a As Single, b As Single)
l = l + 1If l = 4 Then DoEvents: l = 0
If k = 0 Then p(0).X = a: p(0).Y = b
If Pic3.Point(a + 1, b) = vbWhite And Not (Ma(a + 1, b)) Then
j = j + 1
p(j).X = a + 1
p(j).Y = b
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(a, b + 1) = vbWhite And Not (Ma(a, b + 1)) Then
j = j + 1
p(j).X = a
p(j).Y = b + 1
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(a - 1, b) = vbWhite And Not (Ma(a - 1, b)) Then
j = j + 1
p(j).X = a - 1
p(j).Y = b
Ma(p(j).X, p(j).Y) = True
End IfIf Pic3.Point(a, b - 1) = vbWhite And Not (Ma(a, b - 1)) Then
j = j + 1
p(j).X = a
p(j).Y = b - 1
Ma(p(j).X, p(j).Y) = True
End IfPic3.PSet (p(k).X, p(k).Y)
If k = j Then
Exit Sub
End If
k = k + 1
Seed p(k).X, p(k).Y
End Sub
但是现在没有一个好的方法来记时，因为timer 在循环执行时是处于暂停状态的。

Answer 40

To DIPDARK(滴哒):
计时用GetTickCount取得系统开机时间，做差就好了。
同意你的意见，也希望你赶快完成这个算法。如果完成的话，希望大家也能参与到技术的讨论中来。

Answer 41

Linux要自己写的东西更多啊！

Answer 42

To ALL:
本人做好了一个高速SetPixel，现在可以提供给大家样例程序，想要看效果的请留下E-mail。

Answer 43

发过来看看,我也写了一个,不过,
不太好意思拿出来看,还是看看你
的吧,我写Hook还可以,图形算法
实在不怎么样.....  ：）[email protected]谢谢!