Skip to content

Instantly share code, notes, and snippets.

@TheSandvichMaker

TheSandvichMaker/.readme.md

Last active December 28, 2024 22:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save TheSandvichMaker/86baba805952150436cfb481e3a2bd6c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save TheSandvichMaker/86baba805952150436cfb481e3a2bd6c to your computer and use it in GitHub Desktop.
Download ZIP
Implementation of David Eberly's mesh clipping algorithm
Raw
.readme.md
Raw
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)}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment