Category: Computer Graphics

About Laplacian Mesh Optimization

Today I’ve read the paper “Laplacian Mesh Optimization” by Andrew Nealen, Takeo Igarashi, Olga Sorkine, Marc Alexa.

Mesh optimization and Smoothing

Mesh optimization is the reduction of the number of vertices in an initial mesh of triangles without change in the shape. And smoothing is to smooth surface by averaging or removing vertices that is significantly different from other vertices in mesh. Smoothing is performed by subdivision, but the number of vertices is kept in this study.

Novelty of the study

This study introduce a framework for triangle shape optimization and feature preserving smoothing of triangular meshes that is guided by the vertex Laplacians.


Laplacian matrix and Laplacian of vertex

Mesh Graph(V is vertices, E is edges): $$G =\{V, E\}$$

vertices: $$V =[v_1^T, v_2^T,…, v_n^T]^T$$ $$v_i =[v_{ix}, v_{iy},v_{iz}]$$

x, y, z element of vertices: $$V_d =[v_{1d}, v_{2d},…, v_{nd}]^T$$ $$d \in \{x, y, z\}$$

Laplacian of vertex: $$\delta_i =\sum_{\{i,j\} \in E}w_{ij}(v_i, v_j)$$

Weight w is defined below: $$\sum_{\{i,j\} \in E}w_{ij} = 1$$ $$w_{ij} =\frac{\omega_{ij}}{\sum_{\{i,j\} \in E}\omega_{ij}}$$ example for ω: $$\omega_{ij} = 1…(1) $$ $$\omega_{ij} = \cot \alpha + \cot \beta…(2)$$

(1) is uniform weight and (2) is cotangent weight. the angle α and β are defined as follows.

The element of n×n Laplacian Matrix L is define as follows:

x, y, z element of Laplacian: $$\Delta_d =[\delta_{1d}, \delta_{2d},…, \delta_{2d}]^T = LV_d$$ $$d \in \{x, y, z\}$$

the discrete mean curvature normal: $$\overline{\kappa_i}n_i = \delta_{i, c\overline{\kappa_i}}$$ the discrete mean curvature: $$\overline{\kappa_i}$$ the unit length surface normal $$n_i$$

Optimization algorithm

Displaced vertices: $$V’ =[{v’}_1^T, {v’}_2^T,…, {v’}_n^T]^T$$ $$v’_i =[v’_{ix}, v’_{iy},v’_{iz}]$$

x, y, z element of V’: $$V’_d =[v’_{1d}, v’_{2d},…, v’_{nd}]^T$$ $$d \in \{x, y, z\}$$

energy to minimize:

To solve the above problem, an equations of the form AV’_d = b is introduced.

1, Least squares meshes.

2, Detail preserving triangle shape optimization.

The displaced vertices are calculated by the following formula. $$V’_d =(A^TA)^{−1}A^Tb$$

Global triangle shape optimization

In this work, new general 2n×n system AV’_d = b is defined as follows.

W_p is positional weight that constraints vertex position. Larger weights in
W_p preserve the original geometry.

W_L: Laplacian weight that enforce regular triangle shapes and surface smoothness.

L is Laplacian matrix(uniform, cotangent or laplacian with discrete mean curvature ). And f is the corresponding right-hand side with the diagonal matrix W_L.


Check the original paper to see examples of Shape optimization and Smoothing.

[Trouble Shooting] NullFunctionError of glutInit in OpenGL


When trying to call “glutInit()” of PyOpenGL, I got the error “NullFunctionError: Attempt to call an undefined function glutInit, check for bool(glutInit) before calling”.

# python source code
from OpenGL.GL import *
from OpenGL.GLUT import *
from OpenGL.GLU import *

glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB) 
Error Detail

NullFunctionError                         Traceback (most recent call last)
/tmp/ipykernel_14/ in <module>
      3 from OpenGL.GLU import *
----> 5 glutInit()
      6 glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB)

/usr/local/lib/python3.9/site-packages/OpenGL/GLUT/ in glutInit(*args)
    331     try:
    332         # XXX need to check for error condition here...
--> 333         _base_glutInit( ctypes.byref(count), holder )
    334     finally:
    335         os.chdir( currentDirectory )

/usr/local/lib/python3.9/site-packages/OpenGL/platform/ in __call__(self, *args, **named)
    421                 pass
    422             else:
--> 423                 raise error.NullFunctionError(
    424                     """Attempt to call an undefined function %s, check for bool(%s) before calling"""%(
    425                         self.__name__, self.__name__,

NullFunctionError: Attempt to call an undefined function glutInit, check for bool(glutInit) before calling


Python 3.9.7


There are some Recommended Enhancements for PyOpenGL. And some of them, such as GLUT or FreeGLUT, are not contained in PyOpenGL itself.


Solution1 use binary installer for windows.

The documentation says “Win32 and Win64 binary installers for PyOpenGL include a copy of GLUT”.
So uninstall current pyopengl first.
And download binary installer for windows. Put the downloaded file in some directory, then run the command “pip install <file name>” in the directory where the file is saved.

pip uninstall PyOpenGL
pip install PyOpenGL‑3.1.6‑cp39‑cp39‑win_amd64.whl

Solution2 install GLUT or FreeGLUT separately

Installing and adding GLUT or FreeGLUT to PATH solves this problem.

Build FreeGLUT from source code or download built FreeGLUT from “Download freeglut 3.0.0 for MSVC” in

Put freeglut\bin\x64\freeglut.dll into C:\Windows\System32.

Add “C:\Windows\System32” to environment variable “PATH” to enable python find the library.

If the error still occurred, check if your library name is in Win32Platform.GLUT() <python>\Lib\site-packages\OpenGL\platform\

    def GLUT( self ):
        for possible in ('freeglut%s.%s'%(size,vc,), 'freeglut', 'glut%s.%s'%(size,vc,)):  # Added 'freeglut' because the library name is freeglut.dll
            # Prefer FreeGLUT if the user has installed it, fallback to the included 
            # GLUT if it is installed
                return ctypesloader.loadLibrary(
                    ctypes.windll, possible, mode = ctypes.RTLD_GLOBAL
            except WindowsError:
        return None

These links might help you.
python – Attempt to call an undefined function glutInit
#219 glutInit fails on windows 64-bit
Attempt to call an undefined function glutInit
Python and PyOpenGL Installation

Appendix: How to install GLUT or FreeGLUT on Linux

Use “sudo apt-get install python-opengl” command to install PyOpenGL with dependent library at once.

Memorandum of Shadertoy Learning. part1

I’m trying shadertoy these days. This is my tutorial for shadertoy.

1 main function

void mainImage( out vec4 fragColor, in vec2 fragCoord ) is the entry point in Shadertoy.

void mainImage( out vec4 fragColor, in vec2 fragCoord )
 //main drawing process is here

Variable fragCoord contains the pixel coordinates for which the shader needs to compute a color. The resulting color is gathered in fragColor as a four component vector


  • in
    • an “in” variable is used only in this function and not output.
  • out
    • an “out” variable is an output variable that can be passed by reference.
  • inout
    • an “inout” variable is an output and input variable.

2 fragColor

void mainImage( out vec4 fragColor, in vec2 fragCoord )
fragColor = vec4(0.98, 0.808, 0.333, 1.0);

Assign vec4 (R, G, B, alpha) to fragColor variable.

3 fragCoord

variable fragCoord is coordinate of target pixel. fragCoord.x is x coordinate and fragCoord.y is y coordinate and fragCoord.xy is (x,y) coordinate.

void mainImage( out vec4 fragColor, in vec2 fragCoord )
    vec3 color1 = vec3(1.0, 1.0, 0.5);
    vec3 color2 = vec3(0.98, 0.808, 0.333);
    if (int(fragCoord.x )% 50 < 25){
        fragColor = vec4(color1, 1.0);
        fragColor = vec4(color2, 1.0);

4 iResolution

Uniform variable iResolution passes the resolution of the image to the shader. iResolution.x is x coordinate and iResolution.y is y coordinate and iResolution.xy is (x,y) coordinate.

void mainImage( out vec4 fragColor, in vec2 fragCoord )
    int n = 4;
    int width = int(iResolution.x)/n;
    if (int(fragCoord.x )% width < width/2){
        fragColor = vec4(1.0, 1.0, 1.0-fragCoord.y/iResolution.y, 1.0);
        fragColor = vec4(1.0, 0.0, fragCoord.y/iResolution.y, 1.0);

5 Conditional branch and color setting

Check the article “How to Convert HSV to RGB” for more information about hsv2rgb.

vec3 hsv2rgb(in vec3 hsv){
    vec3 rgb;
    float h = hsv.x * 360.0;
    float s = hsv.y;
    float v = hsv.z;
    float c =v * s;
    float h2 = h/60.0;
    float x = c*(1.0 - abs( mod(h2, 2.0) - 1.0));
        case 0: rgb = vec3(v-c) + vec3(c, x, 0.0); return rgb;
        case 1: rgb = vec3(v-c) + vec3(x, c, 0.0); return rgb;
        case 2: rgb = vec3(v-c) + vec3(0.0, c, x); return rgb;
        case 3: rgb = vec3(v-c) + vec3(0.0, x, c); return rgb;
        case 4: rgb = vec3(v-c) + vec3(x, 0.0, c); return rgb;
        case 5: rgb = vec3(v-c) + vec3(c, 0.0, x); return rgb;
        case 6: rgb = vec3(v-c) + vec3(c, x, 0.0); return rgb;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
    vec2 coordinate =  fragCoord.xy - 0.5*iResolution.xy;
    vec3 pixel_color = vec3(0.5);
    int gradation = 10;
    int r_width = int(0.5*iResolution.y/float(gradation));
    int r;
    for(int i =0; i<gradation+1; i++){
        r = r_width*i;
        float i_flaot = float(float(i)/float(gradation+1));
        if(coordinate.x*coordinate.x + coordinate.y*coordinate.y < float(r*r)){
        	pixel_color = hsv2rgb(vec3((1.0/float(gradation))*float(i), 1.0, 1.0));
    fragColor = vec4(pixel_color, 1.0);