如何繪製隱式方程？

01-06

不限2D或3D，類似於將 $x^{2} + y^{2} = 1$ 或者 $x^{2} + y^{2} + z^{2} = 1$ 離散成二維或三維中的點的集合
函數簽名類似於
points pilot( func(x, y){ return [something]; }, minx, miny, maxx, maxy );
使用什麼方法？大致邏輯是什麼？如果有類似數學定理或公式方法名稱提供也可以，我就可以去Google了。。

@叛逆者說的不盡然對。因為你採樣的時候極有可能采不到讓方程剛好成立的地方……

一般的做法是所謂 Marching square/Marching Cube，通過採樣小正方形四角上 f(x, y) 的正負號來近似繪製 f(x, y) = 0。

對三維也差不多

對曲面來說除了 Marching Cube，還有一種三角化方法可以獲得極為均勻的分割

演算法可參閱 http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf 第七章

謝 @空明流轉邀。以下假設你要畫f(x,y) = 0. 演算法的本質是遞歸地在一個像素所對應的二維空間內尋找函數f(x,y)穿越0點的一個證明，或者尋找函數值域不包含0點的證明。如果細分到最後仍然不能證明，那就放棄（可以畫成灰色，但這種情況較為少見）

能證明函數穿過0點的條件是：函數在[x0, x1]x[Y0,Y1] 區間連續，且在四個交點上符號發生變化。

能證明函數不穿過0點的條件是：函數f(x,y)在[x0, x1]X[y0,y1] 區間的上的[保守]值域沒有穿越0點。

所以演算法就是，一開始設定當前判定區間為整個屏幕對應的二維函數空間，判定是否有證明函數不穿越區間的條件，如果有，直接退出。然後判定是否有穿過區間的條件，如果有就把整個屏幕塗成黑色。如果都無法判定，那麼就細分當前空間為四個子空間，分治遞歸。如果當前判定區間對應屏幕空間小於一個像素，那麼在對應此像素的任何一個子空間找到穿越證明後就不再判定這個像素的其他子空間。如果遞歸到一個很大的深度仍然不能作任何判定，那麼就放棄。

至於如何做函數連續性判定和保守值域的計算，請參考interval arithmetic。

如果你使用Windows 8/8.1/10/Windows Phone/RT, 歡迎下載我寫的Equation Sketchpad 應用。這就是對這個演算法的實現。

如果要轉換成矢量數據，一般是使用 marching squares (2D)、marching cubes (3D) [1] 、dual contouring (3D) [2] 等演算法。找到有等值線或等值面的格子時，這些演算法本身是用線性插值去求解，但也可以通過二分法求一條線段上更準確的點，如求 y 在 f(x, y) =0，當中 x=0.1 及 0.9 &< y &< 1.1 。這個問題還有一本專著[3]可參考。

Mikola Lysenko 的 javascript Demo Isosurface Toolbox（源代碼mikolalysenko.github.com/Isosurface at master）[4][5]

如果只要離散像素數據，可參考如何用C語言畫一個「心形」？ - Milo Yip 的回答。在3D下可以用 ray marching 的方法（不過通常是對於距離場的隱式函數用）或是二分法。

另外，如果只需要求一個或數個解，穩式方程 $f(x_0, x_1, ldots)=0$ 應該可以轉化為優化函數 $left | f(x_0, x_1, ldots) ight |$ 的問題。這樣可以通過傳統的數值方法，例如梯度下降法，或對非凸函數用的模擬退火。

[1] Lorensen, William E., and Harvey E. Cline. "Marching cubes: A high resolution 3D surface construction algorithm." ACM siggraph computer graphics. Vol. 21. No. 4. ACM, 1987.

[2] Ju, Tao, et al. "Dual contouring of hermite data." ACM Transactions on Graphics (TOG) 21.3 (2002): 339-346.

[3] Wenger, Rephael. Isosurfaces: geometry, topology, and algorithms. CRC Press, 2013.

[4] Lysenko, Smooth Voxel Terrain (Part 1)

[5] Lysenko, Smooth Voxel Terrain (Part 2)

已經邀請 @Yong He 。

對於兩個變數（f(x,y) = 0）,即任意平面上曲線（按照Paper的要求是，除了有限個間斷點外函數分段可微，實際中是常見數學函數的組合的繪製演算法：

The operators that I have implemented for the graphing
algorithms we will discuss include + ,?, ±, ×, ÷, exponentiation,
nth root, log, min, max, median, minn (nth smallest),
maxn (nth largest), ||, , , !, Γ, seventy-two trigonometric
(multi-)functions (the six basic functions sin, cos, tan,
csc, sec, cot; their functional partial inverses Arcsin, Arccos,
Arctan, Arccsc, Arcsec, Arccot; and their multi-functional
inverses arcsin, arccos, arctan, arccsc, arcsec, arccot; for
trigonometry based on the unit circle x^2 + y^2 = 1, the unit
hyperbola x^2 ? y^2 = 1, the unit diamond |x| + |y| = 1 , and
the unit square max(|x|, |y|) = 1), sgn, mod, gcd, and lcm.

有此文：

http://www.dgp.toronto.edu/~mooncake/papers/SIGGRAPH2001_Tupper.pdf

對於Isosurface的繪製問題，可以參見Wiki

Isosurface

for 離散的每一個點(x, y, z)，如果符合方程，就話個點。

說一下用Ray tracing來處理

圓心在 (0,0,0) ，半徑是 1，可用等式(equation)表示：||x||=1

Ray tracing中繪製物體主要是判斷射線是否與物體相交，如果相交，則對該點進行繪製。

直線與球體有三種位置關係，不相交，相切，穿過，如下圖

一條Ray可以用 r(t)=v+td 表示，帶入方程

若根號內為負數，即相交不發生。另外，由於這裡只需要取最近的交點，因此正負號只需取負號。

而球體在交點的法向量可表示為 n =（p
- c），單位法向量為（p -
c）/R。

可以參考GrafEq的實現

Pedagoguery Software: GrafEq

大概原理是將每個pixel當作一個區間，計算隱函數的估值區間，不包含零就去掉，包含零就繼續細分區間以獲得更準確的結果，具體的可以去看論文

http://www.dgp.toronto.edu/~mooncake/papers/SIGGRAPH2001_Tupper.pdf

二維:

for （double x=-1.0；x 小於等於 1.0； x += 0.01）

{

…y=sqrt（1.0-x*x）;

…linestring.push_point（x,y）;

}

draw linestring...

三維:

for （double x=-1.0；x 小於等於 1.0； x += 0.01）

{

…for （double y=-1.0；y 小於等於 1.0； y+= 0.01）

…{

……z=sqrt（1.0-x*x-y*y）；

……linestring.push_point（x,y,z）;

…}

draw linestring...

知乎文本編輯器對小於號有什麼特殊處理嗎？後面的字全消失了。