Implementation of David Eberly's mesh clipping algorithm

.readme.md

Mesh Clipping

An implementation of David Eberly's mesh clipping algorithm with demo program in odin. See comment at top of file for controls.

clip3d.odin

package clip3d

// Implementation of algorithm described by David Eberly here:
// https://www.geometrictools.com/Documentation/ClipMesh.pdf

// CONTROLS:
// arrows keys to move camera
// number keys to switch view modes:
//   1) basic
//   2) vertices
//   3) edges
//   4) faces
//   5) face inspector
//   6) triangulated "application" mesh
//   7) triangulated mesh edges
//   8) triangulated mesh faces
// T to toggle text
// spacebar to pause/unpause the animation
// shift + left/right arrow to decrease/increase the number of cutting planes
// tap the number key for the current mode to toggle hidden feature visibility or show the triangulated mesh in wireframe
// in face inspector mode, use ctrl + left/right arrow to select a face to inspect
// alt+enter to toggle fullscreen

import    "base:runtime"
		    
import c  "core:c"
import    "core:math"
import    "core:math/linalg"
import    "core:mem"
import    "core:fmt"
import    "core:strings"

import rl "vendor:raylib"

Vec2 :: [2]f32
Vec3 :: [3]f32
Vec4 :: [4]f32

Plane :: struct {
	n: Vec3,	
	d: f32,
}

// "application" mesh

A_Vertex :: Vec3

A_Edge :: struct {
	v0: i32,
	v1: i32,

	f0: i32,
	f1: i32,
}

A_Face :: struct {
	e0: i32,
	e1: i32,
	e2: i32,
}

A_Mesh :: struct {
	V: [dynamic]A_Vertex,
	I: [dynamic]i32,
	E: [dynamic]A_Edge,
	F: [dynamic]A_Face,
}

// clipper mesh

C_Vertex :: struct {
	p        : Vec3,
	distance : f32,
	occurs   : i32,
	visible  : bool,
}

C_Edge :: struct {
	vertex: [2]i32,

	f0: i32,
	f1: i32,

	visible: bool,
}

C_Face :: struct {
	edges   : [dynamic]i32,
	plane   : Plane,
	visible : bool,
}

C_Mesh :: struct {
	V: [dynamic]C_Vertex,
	E: [dynamic]C_Edge,
	F: [dynamic]C_Face,
}

// clipping algorithm

Clip_Result :: enum {
	CLIPPED_NONE,
	CLIPPED_SOME,
	CLIPPED_ALL,
}

clip_mesh_against_planes :: proc(mesh: ^C_Mesh, planes: []Plane) -> Clip_Result {
	result := Clip_Result.CLIPPED_NONE

	for plane in planes {
		EPSILON :: f32(0.0001)

		//
		// vertex processing
		//

		positive, negative := 0, 0
		for &vertex in mesh.V {
			if !vertex.visible do continue

			vertex.distance = linalg.dot(plane.n, vertex.p) - plane.d
			if vertex.distance >= EPSILON {
				positive += 1
			}
			else if vertex.distance <= -EPSILON {
				negative += 1
				vertex.visible = false
			}
			else {
				vertex.distance = 0.0
			}
		} 

		if negative == 0 {
			// all vertices on nonnegative side, no clipping
			continue
		}
		if positive == 0 {
			// all vertices on nonpositive side, everything clipped
			result = .CLIPPED_ALL
			delete_clipper_mesh(mesh)
			break
		}

		//
		// edge processing
		//

		result = .CLIPPED_SOME

		for &edge, edge_index in mesh.E {
			v0 := mesh.V[edge.vertex[0]]
			v1 := mesh.V[edge.vertex[1]]

			d0 := v0.distance
			d1 := v1.distance

			if d0 <= 0 && d1 <= 0 {
				// edge is culled - remove edge from faces sharing it
				if edge.f0 != -1 do remove_edge(&mesh.F[edge.f0], edge_index)
				if edge.f1 != -1 do remove_edge(&mesh.F[edge.f1], edge_index)

				edge.visible = false

				continue
			}

			if d0 >= 0 && d1 >= 0 {
				// edge is on nonnegative side - faces retain the edge
				continue
			}

			// the edge is split by the plane

			t := d0 / (d0 - d1)
			intersect := (1.0 - t)*v0.p + t*v1.p
			index := len(mesh.V)
			append(&mesh.V, C_Vertex{p=intersect, visible=true})

			if d0 > 0 {
				edge.vertex[1] = i32(index)
			}
			else {
				edge.vertex[0] = i32(index)
			}
		}

		// 
		// face processing
		// 

		close_face_index := i32(len(mesh.F))
		append(&mesh.F, C_Face{})

		close_face := &mesh.F[close_face_index]
		close_face.plane   = Plane{-plane.n, plane.d}
		close_face.visible = true

		for &face, face_index in mesh.F {
			if !face.visible do continue

			for edge_index in face.edges {
				mesh.V[mesh.E[edge_index].vertex[0]].occurs = 0
				mesh.V[mesh.E[edge_index].vertex[1]].occurs = 0
			}

			for edge_index in face.edges {
				mesh.V[mesh.E[edge_index].vertex[0]].occurs += 1
				mesh.V[mesh.E[edge_index].vertex[1]].occurs += 1
			}

			start, final := i32(-1), i32(-1)
			for edge_index in face.edges {
				i0 := mesh.E[edge_index].vertex[0]
				i1 := mesh.E[edge_index].vertex[1]

				if mesh.V[i0].occurs == 1 {
					if start == -1 {
						start = i0
					}
					else if final == -1 {
						final = i0
					}
				}

				if mesh.V[i1].occurs == 1 {
					if start == -1 {
						start = i1
					}
					else if final == -1 {
						final = i1
					}
				}

				if start != -1 && final != -1 do break
			}

			if start != -1 {
				// close polyline
				close_edge_index := i32(len(mesh.E))

				close_edge: C_Edge
				close_edge.vertex[0] = start
				close_edge.vertex[1] = final
				close_edge.f0 = i32(face_index)
				close_edge.f1 = close_face_index
				close_edge.visible = true

				append(&mesh.E,           close_edge)
				append(&face.edges,       close_edge_index)
				append(&close_face.edges, close_edge_index)
			}
		}
	}

	return result
}

delete_clipper_mesh :: proc(mesh: ^C_Mesh) {
	delete(mesh.V)
	delete(mesh.E)

	for &face in mesh.F {
		delete(face.edges)
	}

	delete(mesh.F)

	mesh ^= {}
}

remove_edge :: proc(face: ^C_Face, to_remove: int) {
	for edge, edge_index in face.edges {
		if edge == i32(to_remove) {
			unordered_remove(&face.edges, edge_index)
			break
		}
	}

	if len(face.edges) == 0 {
		face.visible = false
	}
}

// convert C_Mesh to A_Mesh

swap :: proc(a: ^$T, b: ^T) { a^, b^ = b^, a^ }

get_ordered_vertices :: proc(mesh_edges: []C_Edge, face_edges: []i32, allocator := context.temp_allocator) -> []i32 {
	edges := make([]i32, len(face_edges), context.temp_allocator)

	for i := 0; i < len(face_edges); i += 1 {
		edges[i] = face_edges[i]
	}

	choice := 1
	for i0 := 0; i0 < len(face_edges) - 2; i0 += 1 {
		i1 := i0 + 1

		current_edge   := &mesh_edges[edges[i0]]
		current_vertex := current_edge.vertex[choice]

		for j := i1; j < len(face_edges); j += 1 {
			edge := &mesh_edges[edges[j]]

			if edge.vertex[0] == current_vertex {
				swap(&edges[i1], &edges[j])
				choice = 1
				break
			}
			
			if edge.vertex[1] == current_vertex {
				swap(&edges[i1], &edges[j])
				choice = 0
				break
			}
		}
	}

	vertices := make([]i32, len(face_edges) + 1, allocator)

	vertices[0] = mesh_edges[edges[0]].vertex[0]
	vertices[1] = mesh_edges[edges[0]].vertex[1]

	for i := 1; i < len(face_edges); i += 1 {
		edge := &mesh_edges[edges[i]]

		if edge.vertex[0] == vertices[i] {
			vertices[i + 1] = edge.vertex[1]
		}
		else {
			vertices[i + 1] = edge.vertex[0]
		}
	}

	return vertices
}

convert_c_mesh_to_a_mesh :: proc(mesh: C_Mesh) -> A_Mesh {
	vertices := make([dynamic]Vec3, allocator=context.temp_allocator)
	vmap     := make([]i32, len(mesh.V), allocator=context.temp_allocator)

	for vertex, i in mesh.V {
		if vertex.visible {
			vmap[i] = i32(len(vertices))
			append(&vertices, vertex.p)
		}
		else {
			vmap[i] = -1
		}
	}

	faces := make([dynamic]i32, allocator=context.temp_allocator)

	// make stream of ordered faces
	for face in mesh.F {
		if !face.visible do continue

		vertices := get_ordered_vertices(mesh.E[:], face.edges[:], context.temp_allocator)
		append(&faces, i32(len(vertices) - 1))

		normal: Vec3
		for i := 0; i < len(vertices) - 1; i += 1 {
			v0 := mesh.V[vertices[i + 0]].p
			v1 := mesh.V[vertices[i + 1]].p
			normal += linalg.cross(v0, v1)
		}
		normal = linalg.normalize(normal)

		if (linalg.dot(face.plane.n, normal) > 0.0) {
			// clockwise, need to swap
			for j := len(vertices) - 2; j >= 0; j -= 1 {
				append(&faces, vmap[vertices[j]])
			}
		}
		else {
			// counter-clockwise
			for j := 0; j <= len(vertices) - 2; j += 1 {
				append(&faces, vmap[vertices[j]])
			}
		}
	}

	result := make_a_mesh_from_vertices_and_ordered_faces(vertices[:], faces[:])
	return result
}

make_a_mesh_from_vertices_and_ordered_faces :: proc(vertices: []Vec3, faces: []i32) -> A_Mesh {
	result: A_Mesh

	append(&result.V, ..vertices)

	// Faces are given as a stream of subarrays, each first a count and then the vertices.
	face_index := i32(0)
	for i := 0; i < len(faces); {
		index_count := faces[i]
		i += 1

		// triangulate with triangle fan
		for j := 1; j < int(index_count) - 1; j += 1 {
			append(&result.I, faces[i + 0])
			append(&result.I, faces[i + j + 1])
			append(&result.I, faces[i + j])
		}

		i += int(index_count)
	}

	// reconstruct edges/faces from triangles
	triangle_count := len(result.I) / 3

	reserve(&result.F, triangle_count)

	Vertex_Tuple :: [2]i32

	sorted_tuple :: proc(v0_, v1_: i32) -> Vertex_Tuple {
		v0, v1 := v0_, v1_

		if v0 > v1 do swap(&v0, &v1)
		return Vertex_Tuple{v0, v1}
	}

	edge_map := make(map[Vertex_Tuple]i32, allocator=context.temp_allocator)

	for face_index := 0; face_index < triangle_count; face_index += 1 {
		v0 := result.I[3*face_index + 0]
		v1 := result.I[3*face_index + 1]
		v2 := result.I[3*face_index + 2]

		tuples := [?]Vertex_Tuple{
			sorted_tuple(v0, v1),
			sorted_tuple(v1, v2),
			sorted_tuple(v2, v0),
		}

		edge_indices: [3]i32

		for tuple, tuple_index in tuples {
			edge_index, ok := edge_map[tuple]

			if ok {
				result.E[edge_index].f1 = i32(face_index)
			}
			else {
				edge_index = i32(len(&result.E))
				append(&result.E, A_Edge{
					v0 = tuple[0],
					v1 = tuple[1],
					f0 = i32(face_index),
				})
				edge_map[tuple] = edge_index
			}

			edge_indices[tuple_index] = edge_index
		}

		append(&result.F, A_Face{
			e0 = edge_indices[0],
			e1 = edge_indices[1],
			e2 = edge_indices[2],
		})
	}

	return result
}

// program

Mode :: enum {
	BASIC,
	VIEW_VERTICES,
	VIEW_EDGES,
	VIEW_FACES,
	INSPECT_FACE,
	VIEW_AMESH,
	VIEW_AMESH_EDGES,
	VIEW_AMESH_FACES,
}

g_mode_feature_toggle: [Mode]bool
g_mode_has_feature_toggle: [Mode]bool = {
	.BASIC            = false,
	.VIEW_VERTICES    = true,
	.VIEW_EDGES       = true,
	.VIEW_FACES       = false,
	.INSPECT_FACE     = false,
	.VIEW_AMESH       = true,
	.VIEW_AMESH_EDGES = true,
	.VIEW_AMESH_FACES = true,
}

g_mode                 : Mode
g_planes               : [dynamic]Plane
g_cutting_planes_count : int
g_inspect_face         : int
g_paused               : bool
g_manual_rotation      : f32
g_fill_triangle_mesh   : bool = true
g_show_text            : bool = true

MAX_SIZE :: Vec3{16, 16, 16}

main :: proc() {
	rl.SetWindowState(rl.ConfigFlags{.WINDOW_RESIZABLE})
	rl.InitWindow(1280, 720, "Clip3D");
	defer rl.CloseWindow()

	rl.SetTargetFPS(60)

	camera: rl.Camera
	camera.position = Vec3{0.8*MAX_SIZE.x, 1.2*MAX_SIZE.x, -2.0*MAX_SIZE.x}
	camera.target   = Vec3{0.0, 0.0, 0.0}
	camera.up       = Vec3{0.0, 1.0, 0.0}
	camera.fovy     = 60.0
	camera.projection = .PERSPECTIVE

	{
		plane: Plane
		plane.n = linalg.normalize(Vec3{1, 1, 1})
		append(&g_planes, plane)
	}

	{
		plane: Plane
		plane.n = linalg.normalize(Vec3{1, 0.5, -0.2})
		append(&g_planes, plane)
	}

	{
		plane: Plane
		plane.n = linalg.normalize(Vec3{-0.3, -0.5, 0.4})
		append(&g_planes, plane)
	}

	// start out with just one
	g_cutting_planes_count = 1

	time := 0.0

	dt       := f32(1.0 / 60.0)
	distance := f32(1.4)

	for (!rl.WindowShouldClose()) {
		if rl.IsKeyDown(.LEFT_ALT) && rl.IsKeyPressed(.ENTER) {
			rl.ToggleBorderlessWindowed()
		}
		
		window_w := rl.GetRenderWidth()
		window_h := rl.GetRenderHeight()

		center := Vec2{ 0.5*f32(window_w), 0.5*f32(window_h) }

		if rl.IsKeyPressed(.SPACE) {
			g_paused = !g_paused
		}

		if rl.IsKeyPressed(.T) {
			g_show_text = !g_show_text
		}

		if rl.IsKeyDown(.LEFT_CONTROL) {
			if g_mode == .INSPECT_FACE {
				if rl.IsKeyPressed(.LEFT) {
					if g_inspect_face > 0 do g_inspect_face -= 1
				}

				if rl.IsKeyPressed(.RIGHT) {
					if g_inspect_face < 32 do g_inspect_face += 1
				}
			}
		}
		else if rl.IsKeyDown(.LEFT_SHIFT) {
			if rl.IsKeyPressed(.LEFT) {
				if g_cutting_planes_count > 0 do g_cutting_planes_count -= 1
			}

			if rl.IsKeyPressed(.RIGHT) {
				if g_cutting_planes_count < len(g_planes) do g_cutting_planes_count += 1
			}
		}
		else {
			if rl.IsKeyDown(.LEFT) {
				g_manual_rotation -= dt
			} 
			if rl.IsKeyDown(.RIGHT) {
				g_manual_rotation += dt
			}
		}

		if rl.IsKeyDown(.DOWN) {
			distance += dt
		}

		if rl.IsKeyDown(.UP) {
			distance -= dt
		}

		// rotate camera
		camera.position.x = distance*MAX_SIZE.x*f32(math.cos(0.1*time + f64(g_manual_rotation)))
		camera.position.z = distance*MAX_SIZE.x*f32(math.sin(0.1*time + f64(g_manual_rotation)))

		g_planes[0].d = 0.5*MAX_SIZE.x*f32(math.sin(time))
		g_planes[1].d = 0.5*MAX_SIZE.x*f32(math.cos(0.7*time))
		g_planes[2].d = 0.3*MAX_SIZE.x*f32(math.sin(-0.3*time) - 0.8)

		planes := g_planes[:g_cutting_planes_count]

		c_mesh := mesh_from_intersection_of_half_spaces(planes)
		defer delete_clipper_mesh(&c_mesh)

		toggle_mode :: proc(mode: Mode) {
			if g_mode == mode {
				g_mode_feature_toggle[g_mode] = !g_mode_feature_toggle[g_mode]
			}

			g_mode = mode
		}

		if rl.IsKeyPressed(.ONE)   do toggle_mode(.BASIC)
		if rl.IsKeyPressed(.TWO)   do toggle_mode(.VIEW_VERTICES)
		if rl.IsKeyPressed(.THREE) do toggle_mode(.VIEW_EDGES)
		if rl.IsKeyPressed(.FOUR)  do toggle_mode(.VIEW_FACES)
		if rl.IsKeyPressed(.FIVE)  do toggle_mode(.INSPECT_FACE)
		if rl.IsKeyPressed(.SIX)   do toggle_mode(.VIEW_AMESH)
		if rl.IsKeyPressed(.SEVEN) do toggle_mode(.VIEW_AMESH_EDGES)
		if rl.IsKeyPressed(.EIGHT) do toggle_mode(.VIEW_AMESH_FACES)

		rl.BeginDrawing()
		rl.ClearBackground(rl.BLACK)

		// mode
		{
			text := strings.clone_to_cstring(fmt.tprintf("mode: %v", g_mode), context.temp_allocator)

			text_color := rl.RAYWHITE
			if g_mode_feature_toggle[g_mode] && g_mode_has_feature_toggle[g_mode] {
				text_color = rl.Color{245, 245, 127, 255}
			}

			rl.DrawText(text, 32, 32, 16, text_color)
		}

		text_offset := c.int(8)

		// 3D rendering

		if g_mode == .VIEW_AMESH {
			rl.BeginMode3D(camera)

			context.allocator = context.temp_allocator
			a_mesh := convert_c_mesh_to_a_mesh(c_mesh)

			show_filled_triangle := !g_mode_feature_toggle[.VIEW_AMESH]

			normal_from_triangle :: proc(a, b, c: Vec3) -> Vec3 {
				ab := b - a
				ac := c - a

				normal := linalg.normalize(linalg.cross(ab, ac))

				return normal
			}

			if show_filled_triangle {
				for i := 0; i < len(a_mesh.I) - 2; i += 3 {
					a := a_mesh.V[a_mesh.I[i + 0]]
					b := a_mesh.V[a_mesh.I[i + 1]]
					c := a_mesh.V[a_mesh.I[i + 2]]

					normal := normal_from_triangle(a, b, c)

					color_f := 0.5 + 0.5*normal

					color: rl.Color
					color.r = u8(255.0*color_f.r)
					color.g = u8(255.0*color_f.g)
					color.b = u8(255.0*color_f.b)
					color.a = 255

					rl.DrawTriangle3D(a, b, c, color)
				}
			}
			
			for i := 0; i < len(a_mesh.I) - 2; i += 3 {
				a := a_mesh.V[a_mesh.I[i + 0]]
				b := a_mesh.V[a_mesh.I[i + 1]]
				c := a_mesh.V[a_mesh.I[i + 2]]

				normal := normal_from_triangle(a, b, c)

				a += 0.02*normal
				b += 0.02*normal
				c += 0.02*normal

				rl.DrawLine3D(a, b, rl.RED)
				rl.DrawLine3D(b, c, rl.RED)
				rl.DrawLine3D(c, a, rl.RED)
			}

			rl.EndMode3D()
		}
		else if g_mode == .VIEW_AMESH_EDGES {
			rl.BeginMode3D(camera)

			context.allocator = context.temp_allocator
			a_mesh := convert_c_mesh_to_a_mesh(c_mesh)

			draw_edge :: proc(mesh: A_Mesh, edge: A_Edge) {
				v0 := mesh.V[edge.v0]
				v1 := mesh.V[edge.v1]
				rl.DrawLine3D(v0, v1, rl.BLUE)
				rl.DrawSphere(v0, 0.1, rl.GREEN)
				rl.DrawSphere(v1, 0.1, rl.GREEN)
			}

			for edge in a_mesh.E {
				draw_edge(a_mesh, edge)
			}
			
			rl.EndMode3D()

			if !g_mode_feature_toggle[.VIEW_AMESH_EDGES] {
				for edge, edge_index in a_mesh.E {
					v0 := a_mesh.V[edge.v0]
					v1 := a_mesh.V[edge.v1]

					center := 0.5*(v0 + v1)
					screen := rl.GetWorldToScreen(center, camera)
					text_color := rl.RAYWHITE

					rl.DrawLineV(screen, screen + f32(text_offset), rl.BLUE)

					text := strings.clone_to_cstring(fmt.tprintf("e%v [f%v f%v]", edge_index, edge.f0, edge.f1), context.temp_allocator)
					rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
				}
			}
		}
		else if g_mode == .VIEW_AMESH_FACES {
			rl.BeginMode3D(camera)

			context.allocator = context.temp_allocator
			a_mesh := convert_c_mesh_to_a_mesh(c_mesh)

			draw_edge :: proc(mesh: A_Mesh, edge: A_Edge) {
				v0 := mesh.V[edge.v0]
				v1 := mesh.V[edge.v1]
				rl.DrawLine3D(v0, v1, rl.YELLOW)
				rl.DrawSphere(v0, 0.1, rl.PINK)
				rl.DrawSphere(v1, 0.1, rl.PINK)
			}

			for face, face_index in a_mesh.F {
				e0 := a_mesh.E[face.e0]
				e1 := a_mesh.E[face.e1]
				e2 := a_mesh.E[face.e2]

				draw_edge(a_mesh, e0)
				draw_edge(a_mesh, e1)
				draw_edge(a_mesh, e2)
			}
			
			rl.EndMode3D()

			if !g_mode_feature_toggle[.VIEW_AMESH_FACES] {
				for face, face_index in a_mesh.F {
					e0 := a_mesh.E[face.e0]
					e1 := a_mesh.E[face.e1]
					e2 := a_mesh.E[face.e1]

					center: Vec3
					center += a_mesh.V[e0.v0]
					center += a_mesh.V[e0.v1]
					center += a_mesh.V[e1.v0]
					center += a_mesh.V[e1.v1]
					center += a_mesh.V[e2.v0]
					center += a_mesh.V[e2.v1]
					center /= 6.0

					screen := rl.GetWorldToScreen(center, camera)
					text_color := rl.RAYWHITE

					t := f32(face_index) / f32(len(a_mesh.F))
					color := rl.ColorFromHSV(360.0*t, 1.0, 1.0)

					rl.DrawCircleV(screen, 4.0, rl.GREEN)
					rl.DrawLineV(screen, screen + f32(text_offset), rl.GREEN)

					text := strings.clone_to_cstring(fmt.tprintf("f%v [e%v e%v e%v]", face_index, face.e0, face.e1, face.e2), context.temp_allocator)
					rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
				}
			}
		}
		else {
			rl.BeginMode3D(camera)

			show_hidden_vertices := g_mode_feature_toggle[.VIEW_VERTICES]
			show_hidden_edges    := g_mode_feature_toggle[.VIEW_EDGES]

			for edge in c_mesh.E {
				if !edge.visible do continue

				p0 := c_mesh.V[edge.vertex[0]]
				p1 := c_mesh.V[edge.vertex[1]]

				color := rl.RED
				if g_mode == .INSPECT_FACE {
					color.a = 127
				}

				rl.DrawLine3D(p0.p, p1.p, color)
			}

			if g_mode == .VIEW_FACES {
				for face, face_index in c_mesh.F {
					if !face.visible do continue

					t := f32(face_index) / f32(len(c_mesh.F))
					color := rl.ColorFromHSV(360.0*t, 1.0, 1.0)
					color.a = face.visible ? 127 : 32

					n := face.plane.n

					for edge, edge_index in face.edges {
						v0 := c_mesh.V[c_mesh.E[edge].vertex[0]]
						v1 := c_mesh.V[c_mesh.E[edge].vertex[1]]

						rl.DrawLine3D(v0.p + 0.1*n, v1.p + 0.1*n, color)
					}
				}
			}

			// draw planes
			for plane in planes {
				p := plane.n*plane.d

				rl.DrawSphere(p, 0.1, rl.BLUE)
				rl.DrawLine3D(p, p + plane.n, rl.BLUE)

				t, b := get_tangent_vectors(plane.n)

				r := MAX_SIZE.x*0.1
				v00 := p - r*t - r*b
				v10 := p + r*t - r*b
				v11 := p + r*t + r*b
				v01 := p - r*t + r*b

				plane_color := rl.BLUE
				plane_color.a = 64

				rl.DrawLine3D(v00, v10, plane_color)
				rl.DrawLine3D(v10, v11, plane_color)
				rl.DrawLine3D(v11, v01, plane_color)
				rl.DrawLine3D(v01, v00, plane_color)
			}

			rl.EndMode3D()

			// 2D rendering

			if g_mode == .VIEW_VERTICES {
				for vert, vert_index in c_mesh.V {
					if !show_hidden_vertices && !vert.visible do continue

					screen := rl.GetWorldToScreen(vert.p, camera)

					color := rl.GREEN
					if !vert.visible do color.a = 48

					rl.DrawCircleV(screen, 8.0, color)

					text_color := rl.RAYWHITE
					if !vert.visible do text_color.a = 48

					text := strings.clone_to_cstring(fmt.tprintf("v%v", vert_index), context.temp_allocator)
					rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
				}

				if g_show_text do print_array("mesh.V", {32, 64}, c_mesh.V[:])
			}

			if g_mode == .VIEW_EDGES {
				for edge, edge_index in c_mesh.E {
					if !show_hidden_edges && !edge.visible do continue

					v0 := c_mesh.V[edge.vertex[0]]
					v1 := c_mesh.V[edge.vertex[1]]

					v0_screen := rl.GetWorldToScreen(v0.p, camera)
					v1_screen := rl.GetWorldToScreen(v1.p, camera)

					screen := rl.GetWorldToScreen(0.5*(v0.p + v1.p), camera)

					color      := rl.BLUE;
					text_color := rl.RAYWHITE;

					if !edge.visible {
						color     .a = 48
						text_color.a = 48
					}

					rl.DrawLineEx(v0_screen, v1_screen, edge.visible ? 2.0 : 1.0, color)

					text := strings.clone_to_cstring(fmt.tprintf("e%v", edge_index), context.temp_allocator)
					rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
				}

				if g_show_text do print_array("mesh.E", {32, 64}, c_mesh.E[:])
			}

			if g_mode == .VIEW_FACES {
				for face, face_index in c_mesh.F {
					if !face.visible do continue

					count    : f32
					center_p : Vec3

					t := f32(face_index) / f32(len(c_mesh.F))
					color := rl.ColorFromHSV(360.0*t, 1.0, 1.0)

					for edge, edge_index in face.edges {
						v0 := c_mesh.V[c_mesh.E[edge].vertex[0]]
						v1 := c_mesh.V[c_mesh.E[edge].vertex[1]]
						center_p += 0.5*(v0.p + v1.p)
						count    += 1.0
					}

					center_p /= count

					normal := face.plane.n

					screen     := rl.GetWorldToScreen(center_p, camera)
					screen_tip := rl.GetWorldToScreen(center_p + 2.0*normal, camera)

					rl.DrawCircleV(screen, 4.0, color)
					rl.DrawLineV(screen, screen_tip, color)
					rl.DrawCircleV(screen_tip, 2.0, color)

					text_color := rl.RAYWHITE

					text := strings.clone_to_cstring(fmt.tprintf("f%v", face_index), context.temp_allocator)
					rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
				}

				if g_show_text do print_array("mesh.F", {32, 64}, c_mesh.F[:])
			}

			if g_mode == .INSPECT_FACE {
				if g_inspect_face < len(c_mesh.F) {
					position := Vec2{32, 64}

					face := &c_mesh.F[g_inspect_face]

					ordered_vertices: []i32

					if face.visible {
						ordered_vertices = get_ordered_vertices(c_mesh.E[:], face.edges[:], context.temp_allocator)
					}

					// edges
					for i := 0; i < len(ordered_vertices) - 1; i += 1 {
						v0 := c_mesh.V[ordered_vertices[i + 0]].p
						v1 := c_mesh.V[ordered_vertices[i + 1]].p

						v0_screen := rl.GetWorldToScreen(v0, camera)
						v1_screen := rl.GetWorldToScreen(v1, camera)

						d_screen    := v1_screen - v0_screen
						perp_screen := linalg.normalize(Vec2{-d_screen.y, d_screen.x})
						arrow0      := 8*(-linalg.normalize(d_screen) + perp_screen)
						arrow1      := 8*(-linalg.normalize(d_screen) - perp_screen)

						rl.DrawLineV(v0_screen, v1_screen, rl.BLUE)
						rl.DrawLineV(v1_screen, v1_screen + arrow0, rl.BLUE)
						rl.DrawLineV(v1_screen, v1_screen + arrow1, rl.BLUE)

						e_screen := 0.5*(v0_screen + v1_screen)
						rl.DrawLineV(e_screen, e_screen + 0.5*arrow0, rl.BLUE)
						rl.DrawLineV(e_screen, e_screen + 0.5*arrow1, rl.BLUE)
					}

					// vertices
					for i := 0; i < len(ordered_vertices) - 1; i += 1 {
						v0        := c_mesh.V[ordered_vertices[i]].p
						v0_screen := rl.GetWorldToScreen(v0, camera)

						color := i == 0 ? rl.YELLOW : rl.GREEN
						rl.DrawCircleV(v0_screen, 4.0, color)
					}

					if g_show_text do position = print_item(fmt.tprintf("face[%v]", g_inspect_face), position, face)
					position.y += 2

					for edge_index in face.edges {
						edge := c_mesh.E[edge_index]
						if g_show_text do position = print_item(fmt.tprintf("e%v", edge_index), position, edge)

						v0 := c_mesh.V[edge.vertex[0]]
						v1 := c_mesh.V[edge.vertex[1]]

						v0_screen := rl.GetWorldToScreen(v0.p, camera)
						v1_screen := rl.GetWorldToScreen(v1.p, camera)

						screen := rl.GetWorldToScreen(0.5*(v0.p + v1.p), camera)

						{
							color      := edge.visible ? rl.BLUE     : rl.Color{24, 32, 64, 255}
							text_color := edge.visible ? rl.RAYWHITE : rl.Color{64, 64, 64, 255}

							text := strings.clone_to_cstring(fmt.tprintf("e%v", edge_index), context.temp_allocator)
							rl.DrawText(text, c.int(screen.x) + text_offset, c.int(screen.y) + text_offset, 16, text_color)
						}

						{
							text := strings.clone_to_cstring(fmt.tprintf("v%v", edge.vertex[0]), context.temp_allocator)
							rl.DrawText(text, c.int(v0_screen.x) + text_offset, c.int(v0_screen.y) + text_offset, 16, rl.RAYWHITE)
						}

						{
							text := strings.clone_to_cstring(fmt.tprintf("v%v", edge.vertex[1]), context.temp_allocator)
							rl.DrawText(text, c.int(v1_screen.x) + text_offset, c.int(v1_screen.y) + text_offset, 16, rl.RAYWHITE)
						}
					}

					position.y += 2

					if g_show_text && face.visible {
						text := strings.clone_to_cstring(fmt.tprintf("ordered_vertices = %v", ordered_vertices), context.temp_allocator)
						rl.DrawText(text, c.int(position.x), c.int(position.y), 18, rl.RAYWHITE)
					}
				}
			}
		}

		{
			text := strings.clone_to_cstring(fmt.tprintf("cutting planes count: %v", g_cutting_planes_count), context.temp_allocator)
			text_color := rl.RAYWHITE
			
			if rl.IsKeyDown(.LEFT_SHIFT) {
				text_color = rl.BLUE
			}

			rl.DrawText(text, 32, c.int(window_h) - 32, 18, text_color)
		}

		rl.EndDrawing()

		if !g_paused {
			time += 1.0 / 60.0
		}

		mem.free_all(context.temp_allocator)
	}
}

// initial cube

make_cube_clipper_mesh :: proc(initial_size: Vec3) -> C_Mesh {
	mesh: C_Mesh

	r := 0.5*initial_size

	// diagram (both views are top down looking down the negative y axis)
	//
	//              bottom                            top
    //                f3
    //                 v                     e11                e10
    //                                         \                /
	//          v3 --- e2 --- v2                v7 --- e6 --- v6
	//          |              |                |              |
	//          |              |                |              |
	//    f4 >  e3     f0     e1  < f2          e7     f5     e5
	//          |              |                |              |
	//          |              |                |              |
	//          v0 --- e0 --- v1                v4 --- e4 --- v5
	//                                         /                \
	//                  ^                    e8                 e9
	//     ^           f1
	//     |
	//  +z |
	//     -------->
	//     +x

	//
	// bottom quad
	//

	// vertices
	append(&mesh.V, C_Vertex{p={-r.x, -r.y, -r.z}, visible=true}) // v0
	append(&mesh.V, C_Vertex{p={ r.x, -r.y, -r.z}, visible=true}) // v1
	append(&mesh.V, C_Vertex{p={ r.x, -r.y,  r.z}, visible=true}) // v2
	append(&mesh.V, C_Vertex{p={-r.x, -r.y,  r.z}, visible=true}) // v3

	// edges
	append(&mesh.E, C_Edge{{0, 1}, 0, 1, true}) // e0
	append(&mesh.E, C_Edge{{1, 2}, 0, 2, true}) // e1
	append(&mesh.E, C_Edge{{2, 3}, 0, 3, true}) // e2
	append(&mesh.E, C_Edge{{3, 0}, 0, 4, true}) // e3

	//
	// top quad
	//

	// vertices
	append(&mesh.V, C_Vertex{p={-r.x,  r.y, -r.z}, visible=true}) // v4
	append(&mesh.V, C_Vertex{p={ r.x,  r.y, -r.z}, visible=true}) // v5
	append(&mesh.V, C_Vertex{p={ r.x,  r.y,  r.z}, visible=true}) // v6
	append(&mesh.V, C_Vertex{p={-r.x,  r.y,  r.z}, visible=true}) // v7

	// edges
	append(&mesh.E, C_Edge{{4, 5}, 5, 1, true}) // e4
	append(&mesh.E, C_Edge{{5, 6}, 5, 2, true}) // e5
	append(&mesh.E, C_Edge{{6, 7}, 5, 3, true}) // e6
	append(&mesh.E, C_Edge{{7, 4}, 5, 4, true}) // e7

	//
	// "column" edges
	//

	append(&mesh.E, C_Edge{{0, 4}, 4, 1, true}) // e8
	append(&mesh.E, C_Edge{{1, 5}, 1, 2, true}) // e9
	append(&mesh.E, C_Edge{{2, 6}, 2, 3, true}) // e10
	append(&mesh.E, C_Edge{{3, 7}, 3, 4, true}) // e11

	//
	// faces
	//

	append(&mesh.F, C_Face{edges=[dynamic]i32{0, 1,  2,  3}, plane={{ 0, -1,  0}, r.y}, visible=true}) // f0
	append(&mesh.F, C_Face{edges=[dynamic]i32{0, 9,  4,  8}, plane={{ 0,  0, -1}, r.z}, visible=true}) // f1
	append(&mesh.F, C_Face{edges=[dynamic]i32{1, 10, 5,  9}, plane={{ 1,  0,  0}, r.x}, visible=true}) // f2
	append(&mesh.F, C_Face{edges=[dynamic]i32{2, 11, 6, 10}, plane={{ 0,  0,  1}, r.z}, visible=true}) // f3
	append(&mesh.F, C_Face{edges=[dynamic]i32{3, 8,  7, 11}, plane={{-1,  0,  0}, r.x}, visible=true}) // f4
	append(&mesh.F, C_Face{edges=[dynamic]i32{4, 5,  6,  7}, plane={{ 0,  1,  0}, r.y}, visible=true}) // f5

	return mesh
}

mesh_from_intersection_of_half_spaces :: proc(planes: []Plane) -> C_Mesh {
	mesh := make_cube_clipper_mesh(MAX_SIZE)

	clip_mesh_against_planes(&mesh, planes)

	return mesh
}

// misc helpers

get_tangent_vectors :: proc(n: Vec3) -> (Vec3, Vec3) {
    up := Vec3{0, 1, 0};

    t, b: Vec3
    t = linalg.cross(up, n);

    if linalg.length(t) <= 0.01
    {
        up = Vec3{0, 0, 1}
        t = linalg.cross(up, n);
    }

    t = linalg.normalize(t);
    b = linalg.normalize(linalg.cross(n, t));

    return t, b
}

print_item :: proc(name: string, position: Vec2, item: $T, font_size := c.int(18), color := rl.RAYWHITE) -> Vec2 {
	x := c.int(position.x)
	y := c.int(position.y)

	text := strings.clone_to_cstring(fmt.tprintf("%v = %v", name, item), context.temp_allocator)

	actual_color := item.visible ? color : rl.Color{64, 64, 64, 255}

	rl.DrawText(text, x, y, font_size, actual_color)
	y += font_size + 2

	return Vec2{f32(x), f32(y)}
}

print_array :: proc(name: string, position: Vec2, array: []$T, font_size := c.int(18), color := rl.RAYWHITE) -> Vec2 {
	x := c.int(position.x)
	y := c.int(position.y)

	for item, index in array {
		text := strings.clone_to_cstring(fmt.tprintf("%v[%v] = %v", name, index, item), context.temp_allocator)

		actual_color := item.visible ? color : rl.Color{64, 64, 64, 255}

		rl.DrawText(text, x, y, font_size, actual_color)
		y += font_size + 2
	}

	return Vec2{f32(x), f32(y)}
}