dymokomi/luce-geocore
Source of release 0.7.4
0.7.4 / src / code / queries.lucb
# Spatial reads: nearest points (a point grid), the closest surface point and its uv
# (the faces' spatial index), interpolation at a uv, ray hits and bounds.
#
# A primitive's uv is parametric over its display triangles: `u = t + a`, `v = b` on its
# triangle `t` (corners A, B, C) for the point `A + a (B - A) + b (C - A)`, so a triangle's
# uv is its barycentric one and every uv `closest_uv` or `intersect` gives reads back
# with `primuv_*` at the same place.
## The position argument starting at argument `first` (four lanes), as f64.
func position_argument(call: const engine.Call*, first: usize, lane: usize) -> Vector3:
return Vector3((f64)call.f32_argument(first)[lane], (f64)call.f32_argument(first + 1)[lane], (f64)call.f32_argument(first + 2)[lane])
func nearpoint(call: engine.Call*):
let state = state_of(call) else return
let reach = call.f32_argument(5)
let points = call.i32_result(0)
var found: u32[16]
var distances: f64[16]
for lane in 0..<call.lanes:
points[lane] = -1
let source = source_or_fail(state, call, lane) else continue
if source.mesh == none: continue
if not source.with_grid():
call.fail(lane)
continue
if source.grid.nearest(position_argument(call, 1, lane), (f64)reach[lane], 1, found, distances) > 0:
points[lane] = (i32)found[0]
func nearpoints(call: engine.Call*):
let state = state_of(call) else return
let reach = call.f32_argument(5)
let most = call.i32_argument(6)
var found: u32[16]
var distances: f64[16]
# The result columns, fetched once: the count, then the 16 point numbers.
let counts = call.i32_result(0)
var columns: (i32[])[16]
for k: usize in 0..<16: columns[k] = call.i32_result(1 + k)
for lane in 0..<call.lanes:
var count: usize = 0
if let source = source_or_fail(state, call, lane):
if source.mesh != none:
if source.with_grid():
let limit = 0 if most[lane] < 0 else (16 if most[lane] > 16 else (usize)most[lane])
count = source.grid.nearest(position_argument(call, 1, lane), (f64)reach[lane], limit, found, distances)
else:
call.fail(lane)
counts[lane] = (i32)count
for k: usize in 0..<16:
columns[k][lane] = (i32)found[k] if k < count else -1
## The nearest face to `p` and its distance, or (-1, -1.0) with no surface. With
## `bound` >= 0 (an upper bound on the answer, as a neighboring lane's distance plus
## how far `p` is from it) the search prunes with it and `hint`, the face at most
## `bound` away, answers when nothing is closer; a tie may then answer with either face.
func nearest_face(source: Source*, p: Vector3, hint: i64, bound: f64) -> (i64, f64)!:
let mesh = source.mesh else return (-1, -1.0)
if mesh.face_count() == 0: return (-1, -1.0)
if not source.with_queries(): error(errors.invalid, "the surface index could not be built")
let index = source.index else return (-1, -1.0)
let local = p.subtract(mesh.position_origin())
if hint >= 0 and bound >= 0.0:
let hit = index.nearest_within(local, bound * 1.000001 + 1.0e-12)
if hit.face >= 0: return (hit.face, hit.distance)
let (near, _, _) = closest_on_face(mesh, (usize)hint, p)
let d = near.subtract(p)
return (hint, math.sqrt(d.dot(d)))
let hit = index.nearest(local)
return (hit.face, hit.distance)
## The closest surface point to `p`: its face (-1 for no surface), distance, and uv.
func closest(source: Source*, p: Vector3) -> (i64, f64, f64, f64)!:
let mesh = source.mesh else return (-1, -1.0, 0.0, 0.0)
let (face, _) = try nearest_face(source, p, -1, -1.0)
if face < 0: return (-1, -1.0, 0.0, 0.0)
let (point, u, v) = closest_on_face(mesh, (usize)face, p)
let d = point.subtract(p)
return (face, math.sqrt(d.dot(d)), u, v)
## Distances to the surface; consecutive lanes are usually neighbors, so each
## search is bounded by the last answer plus the step between the points.
func xyzdist(call: engine.Call*):
let state = state_of(call) else return
let distances = call.f32_result(0)
var hint: i64 = -1
var last_distance = -1.0
var last_point = Vector3()
for lane in 0..<call.lanes:
distances[lane] = -1.0
let source = source_or_fail(state, call, lane) else continue
let p = position_argument(call, 1, lane)
let step = p.subtract(last_point)
let bound = last_distance + math.sqrt(step.dot(step)) if hint >= 0 else -1.0
let (face, distance) = nearest_face(source, p, hint, bound) catch failure:
_ = failure
call.fail(lane)
continue
hint = face
last_distance = distance
last_point = p
distances[lane] = (f32)distance
func closest_prim(call: engine.Call*):
let state = state_of(call) else return
let prims = call.i32_result(0)
for lane in 0..<call.lanes:
prims[lane] = -1
let source = source_or_fail(state, call, lane) else continue
let found = closest(source, position_argument(call, 1, lane)) catch failure:
_ = failure
call.fail(lane)
continue
prims[lane] = (i32)found.0
func closest_uv(call: engine.Call*):
let state = state_of(call) else return
for lane in 0..<call.lanes:
call.f32_result(0)[lane] = 0.0
call.f32_result(1)[lane] = 0.0
let source = source_or_fail(state, call, lane) else continue
let found = closest(source, position_argument(call, 1, lane)) catch failure:
_ = failure
call.fail(lane)
continue
call.f32_result(0)[lane] = (f32)found.2
call.f32_result(1)[lane] = (f32)found.3
## The closest point of face `face` to `p` (world) over its display triangles, and its uv.
func closest_on_face(mesh: const Mesh*, face: usize, p: Vector3) -> (Vector3, f64, f64):
let offsets = mesh.offset_span()
let corners = mesh.corner_span()
let triangles = mesh.triangle_span()
let start = (usize)offsets[face]
let size = (usize)offsets[face + 1] - start
let base = (start - face * 2) * 3
var best = Vector3()
var best_distance: f64 = 1.0e300
var best_u: f64 = 0.0
var best_v: f64 = 0.0
for t in 0..<size - 2:
let a = world_point(mesh, corners[(usize)triangles[base + t * 3]])
let b = world_point(mesh, corners[(usize)triangles[base + t * 3 + 1]])
let c = world_point(mesh, corners[(usize)triangles[base + t * 3 + 2]])
let (point, u, v) = closest_on_triangle(p, a, b, c)
let d = point.subtract(p)
let distance = d.dot(d)
if distance < best_distance:
best_distance = distance
best = point
best_u = (f64)t + math.min(u, 0.999999)
best_v = v
return (best, best_u, best_v)
func world_point(mesh: const Mesh*, point: i32) -> Vector3:
return mesh.point_span()[(usize)point].vector().add(mesh.position_origin())
## The closest point of triangle ABC to `p` and its barycentric (u, v): `A + u (B - A) +
## v (C - A)` (Ericson, Real-Time Collision Detection 5.1.5).
func closest_on_triangle(p: Vector3, a: Vector3, b: Vector3, c: Vector3) -> (Vector3, f64, f64):
let ab = b.subtract(a)
let ac = c.subtract(a)
let ap = p.subtract(a)
let d1 = ab.dot(ap)
let d2 = ac.dot(ap)
if d1 <= 0.0 and d2 <= 0.0: return (a, 0.0, 0.0)
let bp = p.subtract(b)
let d3 = ab.dot(bp)
let d4 = ac.dot(bp)
if d3 >= 0.0 and d4 <= d3: return (b, 1.0, 0.0)
let vc = d1 * d4 - d3 * d2
if vc <= 0.0 and d1 >= 0.0 and d3 <= 0.0:
let u = d1 / (d1 - d3)
return (a.add(ab.multiply_scalar(u)), u, 0.0)
let cp = p.subtract(c)
let d5 = ab.dot(cp)
let d6 = ac.dot(cp)
if d6 >= 0.0 and d5 <= d6: return (c, 0.0, 1.0)
let vb = d5 * d2 - d1 * d6
if vb <= 0.0 and d2 >= 0.0 and d6 <= 0.0:
let v = d2 / (d2 - d6)
return (a.add(ac.multiply_scalar(v)), 0.0, v)
let va = d3 * d6 - d5 * d4
if va <= 0.0 and (d4 - d3) >= 0.0 and (d5 - d6) >= 0.0:
let w = (d4 - d3) / ((d4 - d3) + (d5 - d6))
return (b.add(c.subtract(b).multiply_scalar(w)), 1.0 - w, w)
let denominator = 1.0 / (va + vb + vc)
let v = vb * denominator
let w = vc * denominator
return (a.add(ab.multiply_scalar(v)).add(ac.multiply_scalar(w)), v, w)
## `name` ("P": positions) interpolated at `uv` on face `face`: point and vertex
## attributes over the uv's triangle, a primitive attribute as it is.
func interpolated(mesh: const Mesh*, face: usize, u: f64, v: f64, name: str, out: f64[]):
let offsets = mesh.offset_span()
let corners = mesh.corner_span()
let triangles = mesh.triangle_span()
let start = (usize)offsets[face]
let size = (usize)offsets[face + 1] - start
let base = (start - face * 2) * 3
let raw = math.floor(u)
var t: usize = 0
if raw > 0.0: t = (usize)raw if raw < (f64)(size - 2) else size - 3
let a = u - (f64)t
let weights: f64[3] = [1.0 - a - v, a, v]
let three: usize[3] = [(usize)triangles[base + t * 3], (usize)triangles[base + t * 3 + 1], (usize)triangles[base + t * 3 + 2]]
for k in 0..<out.length: out[k] = 0.0
if name == "P":
for (at, corner) in three.indexed():
let point = world_point(mesh, corners[corner])
out[0] += weights[at] * point.x
if out.length > 1:
out[1] += weights[at] * point.y
out[2] += weights[at] * point.z
return
for domain in [Domain.point, Domain.corner, Domain.face]:
let found = mesh.find_attribute(name, (i64)(u8)domain)
if found < 0: continue
let entry = mesh.attribute_entry(found) catch failure: return
let lanes = out.length if out.length < entry.width else entry.width
if domain == .face:
for k in 0..<lanes: out[k] = entry.number(face, k)
return
for (at, corner) in three.indexed():
let element = (usize)corners[corner] if domain == .point else corner
for k in 0..<lanes: out[k] += weights[at] * entry.number(element, k)
return
func primuv(call: engine.Call*):
let state = state_of(call) else return
let context = call.context else return
let lanes = *(const usize*)context
let prims = call.i32_argument(1)
let us = call.f32_argument(2)
let vs = call.f32_argument(3)
let name = call.text(0)
var values: f64[3]
for lane in 0..<call.lanes:
let source = source_or_fail(state, call, lane) else continue
let mesh = mesh_or_fail(source, call, lane) else continue
let face = element_or_fail(call, lane, prims[lane], source.prims()) else continue
interpolated(mesh, face, (f64)us[lane], (f64)vs[lane], name, values[..<lanes])
if lanes == 1:
call.f32_result(0)[lane] = (f32)values[0]
else:
write_vector(call, 0, lane, Vector3(values[0], values[1], values[2]))
func intersect(call: engine.Call*):
let state = state_of(call) else return
for lane in 0..<call.lanes:
call.i32_result(0)[lane] = -1
call.f32_result(1)[lane] = 0.0
call.f32_result(2)[lane] = 0.0
write_vector(call, 3, lane, Vector3())
call.f32_result(7)[lane] = -1.0
let source = source_or_fail(state, call, lane) else continue
let mesh = source.mesh else continue
if mesh.face_count() == 0: continue
if not source.with_queries():
call.fail(lane)
continue
let origin = position_argument(call, 1, lane)
let toward = position_argument(call, 5, lane)
let length = math.sqrt(toward.dot(toward))
if not (length > 0.0): continue
let direction = toward.multiply_scalar(1.0 / length)
let index = source.index else continue
let hit = index.ray(origin.subtract(mesh.position_origin()), direction)
let face = hit.face
let distance = hit.distance
if face < 0: continue
let position = origin.add(direction.multiply_scalar(distance))
let (point, u, v) = closest_on_face(mesh, (usize)face, position)
_ = point
call.i32_result(0)[lane] = (i32)face
call.f32_result(1)[lane] = (f32)u
call.f32_result(2)[lane] = (f32)v
write_vector(call, 3, lane, position)
call.f32_result(7)[lane] = (f32)distance
func bounds(call: engine.Call*):
let state = state_of(call) else return
for lane in 0..<call.lanes:
var low = Vector3()
var high = Vector3()
if let source = source_or_fail(state, call, lane):
if let mesh = source.mesh:
if mesh.point_count() > 0:
let box = mesh.bounds()
low = box.minimum
high = box.maximum
write_vector(call, 0, lane, low)
write_vector(call, 4, lane, high)
write_vector(call, 8, lane, low.add(high).multiply_scalar(0.5))
write_vector(call, 12, lane, high.subtract(low))