Skip to main content

meshoptimizer_rs/
partition.rs

1// Port of meshoptimizer 1.3 partition.cpp (MIT, Arseny Kapoulkine).
2use crate::processing::{dot, finite, point, sub, Context};
3use crate::{Error, Positions, Workspace};
4use alloc::vec::Vec;
5/// Cluster-to-partition assignments in upstream order.
6#[derive(Debug, Default, PartialEq, Eq)]
7pub struct Partitions {
8    /// Partition id for each input cluster.
9    pub assignments: Vec<u32>,
10    /// Number of partitions.
11    pub count: usize,
12}
13#[derive(Clone, Copy, Default)]
14struct Group {
15    group: i32,
16    next: i32,
17    size: u32,
18    vertices: u32,
19    center: [f32; 3],
20    radius: f32,
21}
22#[derive(Clone, Copy, Default)]
23struct Order {
24    id: u32,
25    order: i32,
26}
27fn push(heap: &mut [Order], n: &mut usize, item: Order) {
28    let mut i = *n;
29    heap[i] = item;
30    *n += 1;
31    while i > 0 && heap[i].order < heap[(i - 1) / 2].order {
32        let p = (i - 1) / 2;
33        heap.swap(i, p);
34        i = p;
35    }
36}
37fn pop(heap: &mut [Order], n: &mut usize) -> Order {
38    let top = heap[0];
39    *n -= 1;
40    heap[0] = heap[*n];
41    let mut i = 0;
42    while i * 2 + 1 < *n {
43        let mut j = i * 2 + 1;
44        if j + 1 < *n && heap[j + 1].order < heap[j].order {
45            j += 1;
46        }
47        if heap[j].order >= heap[i].order {
48            break;
49        }
50        heap.swap(i, j);
51        i = j;
52    }
53    top
54}
55fn score(a: Group, b: Group, ctx: &mut Context<'_>) -> Result<f32, Error> {
56    let dp = sub(b.center, a.center);
57    let d = ctx.sqrt(finite(dot(dp, dp))?);
58    let mr = if d + a.radius < b.radius {
59        b.radius
60    } else if d + b.radius < a.radius {
61        a.radius
62    } else {
63        (d + b.radius + a.radius) / 2.
64    };
65    finite(if mr > 0. { a.radius / mr } else { 0. })
66}
67fn merge(a: &mut Group, b: Group, ctx: &mut Context<'_>) -> Result<(), Error> {
68    let dp = sub(b.center, a.center);
69    let d = ctx.sqrt(finite(dot(dp, dp))?);
70    if d + a.radius < b.radius {
71        a.center = b.center;
72        a.radius = b.radius;
73    } else if d + b.radius > a.radius {
74        let k = if d > 0. {
75            (d + b.radius - a.radius) / (2. * d)
76        } else {
77            0.
78        };
79        for (j, &v) in dp.iter().enumerate() {
80            a.center[j] = finite(a.center[j] + v * k)?;
81        }
82        a.radius = finite((d + b.radius + a.radius) / 2.)?;
83    }
84    Ok(())
85}
86fn leaf(
87    groups: &mut [Group],
88    order: &[u32],
89    target: usize,
90    max: usize,
91    ctx: &mut Context<'_>,
92) -> Result<(), Error> {
93    for &id in order {
94        let id = id as usize;
95        if groups[id].size == 0 || groups[id].size as usize >= target {
96            continue;
97        }
98        let mut best = None;
99        let mut bestscore = -1.;
100        for &other in order {
101            ctx.tick(1)?;
102            let other = other as usize;
103            if id == other
104                || groups[other].size == 0
105                || (groups[id].size as usize + groups[other].size as usize) > max
106            {
107                continue;
108            }
109            let sc = score(groups[id], groups[other], ctx)?;
110            if sc > bestscore {
111                best = Some(other);
112                bestscore = sc;
113            }
114        }
115        if let Some(other) = best {
116            let mut tail = other;
117            while groups[tail].next >= 0 {
118                ctx.tick(1)?;
119                tail = groups[tail].next as usize;
120            }
121            groups[tail].next = id as i32;
122            groups[other].size += groups[id].size;
123            groups[id].size = 0;
124            let g = groups[id];
125            merge(&mut groups[other], g, ctx)?;
126            groups[id].radius = 0.;
127        }
128    }
129    Ok(())
130}
131fn spatial(
132    groups: &mut [Group],
133    order: &mut [u32],
134    target: usize,
135    max: usize,
136    depth: usize,
137    ctx: &mut Context<'_>,
138) -> Result<(), Error> {
139    ctx.tick(order.len())?;
140    let total = order
141        .iter()
142        .map(|&v| groups[v as usize].size as usize)
143        .sum::<usize>();
144    if total <= max || order.len() <= 8 {
145        return leaf(groups, order, target, max, ctx);
146    }
147    let mut mean = [0.; 3];
148    let mut vars = [0.; 3];
149    let mut runc = 1.;
150    let mut runs = 1.;
151    ctx.tick(order.len() * 2)?;
152    for &v in order.iter() {
153        let p = groups[v as usize].center;
154        for k in 0..3 {
155            let delta = p[k] - mean[k];
156            mean[k] += delta * runs;
157            vars[k] += delta * (p[k] - mean[k]);
158        }
159        runc += 1.;
160        runs = 1. / runc;
161    }
162    let axis = if vars[0] >= vars[1] && vars[0] >= vars[2] {
163        0
164    } else if vars[1] >= vars[2] {
165        1
166    } else {
167        2
168    };
169    let mut middle = 0;
170    for i in 0..order.len() {
171        let v = groups[order[i] as usize].center[axis];
172        order.swap(middle, i);
173        middle += usize::from(v < mean[axis]);
174    }
175    if middle <= 4 || order.len() - middle <= 4 || depth >= 40 {
176        middle = order.len() / 2;
177    }
178    let (left, right) = order.split_at_mut(middle);
179    spatial(groups, left, target, max, depth + 1, ctx)?;
180    spatial(groups, right, target, max, depth + 1, ctx)
181}
182struct Adj {
183    offsets: Vec<u32>,
184    clusters: Vec<u32>,
185    shared: Vec<u32>,
186}
187fn adjacent(
188    indices: &[u32],
189    offsets: &[u32],
190    n: usize,
191    vertices: usize,
192    ctx: &mut Context<'_>,
193) -> Result<Adj, Error> {
194    let mut refs = ctx.alloc::<u32>(vertices + 1)?;
195    ctx.tick(indices.len())?;
196    for &v in indices {
197        refs[v as usize] += 1;
198    }
199    let mut total = 0usize;
200    for i in 0..n {
201        let mut count = 0usize;
202        // Batched visit charges (ctx.scan) keep each per-visit exhaustion point.
203        ctx.scan(
204            indices[offsets[i] as usize..offsets[i + 1] as usize].iter(),
205            |_, &v| {
206                count = count
207                    .checked_add(refs[v as usize] as usize - 1)
208                    .ok_or(Error::SizeOverflow)?;
209                Ok(())
210            },
211        )?;
212        total = total
213            .checked_add(count.min(n - 1))
214            .ok_or(Error::SizeOverflow)?;
215    }
216    if total > u32::MAX as usize {
217        return Err(Error::SizeOverflow);
218    }
219    let mut adj = Adj {
220        offsets: ctx.alloc(n + 1)?,
221        clusters: ctx.alloc(total)?,
222        shared: ctx.alloc(total)?,
223    };
224    let mut nr = 0;
225    for r in &mut refs[..vertices] {
226        let n = *r;
227        *r = nr;
228        nr += n;
229    }
230    let mut data = ctx.alloc::<u32>(nr as usize)?;
231    for i in 0..n {
232        ctx.scan(
233            indices[offsets[i] as usize..offsets[i + 1] as usize].iter(),
234            |_, &v| {
235                let r = &mut refs[v as usize];
236                data[*r as usize] = i as u32;
237                *r += 1;
238                Ok(())
239            },
240        )?;
241    }
242    refs.copy_within(0..vertices, 1);
243    refs[0] = 0;
244    let mut slots = ctx.alloc::<u32>(n)?;
245    slots.fill(u32::MAX);
246    for i in 0..n {
247        let start = adj.offsets[i] as usize;
248        let mut count = 0;
249        for &v in &indices[offsets[i] as usize..offsets[i + 1] as usize] {
250            let others = &data[refs[v as usize] as usize..refs[v as usize + 1] as usize];
251            // These visits cannot fail: charge a covered list once, otherwise
252            // keep the per-visit exhaustion point.
253            let batched = ctx.work.covers(others.len())?;
254            for &c in others {
255                if !batched {
256                    ctx.tick(1)?;
257                }
258                if c as usize == i {
259                    continue;
260                }
261                let slot = slots[c as usize] as usize;
262                if slot < count && adj.clusters[start + slot] == c {
263                    adj.shared[start + slot] += 1;
264                } else {
265                    slots[c as usize] = count as u32;
266                    adj.clusters[start + count] = c;
267                    adj.shared[start + count] = 1;
268                    count += 1;
269                }
270            }
271            if batched {
272                ctx.tick(others.len())?;
273            }
274        }
275        adj.offsets[i + 1] = (start + count) as u32;
276    }
277    ctx.release(&refs)?;
278    ctx.release(&data)?;
279    ctx.release(&slots)?;
280    Ok(adj)
281}
282fn pick(
283    groups: &[Group],
284    id: usize,
285    adj: &Adj,
286    max: usize,
287    bounds: bool,
288    acc: &mut [u32],
289    ctx: &mut Context<'_>,
290) -> Result<Option<(usize, u32)>, Error> {
291    let r = 1. / ctx.sqrt(groups[id].vertices as i32 as f32);
292    let mut ci = id as i32;
293    while ci >= 0 {
294        let c = ci as usize;
295        ctx.tick((adj.offsets[c + 1] - adj.offsets[c]) as usize)?;
296        for i in adj.offsets[c] as usize..adj.offsets[c + 1] as usize {
297            let other = groups[adj.clusters[i] as usize].group;
298            if other >= 0 {
299                acc[other as usize] = acc[other as usize]
300                    .checked_add(adj.shared[i])
301                    .ok_or(Error::SizeOverflow)?;
302            }
303        }
304        ci = groups[c].next;
305    }
306    let mut best = None;
307    let mut bestscore = 0.;
308    ci = id as i32;
309    while ci >= 0 {
310        let c = ci as usize;
311        ctx.tick((adj.offsets[c + 1] - adj.offsets[c]) as usize)?;
312        for i in adj.offsets[c] as usize..adj.offsets[c + 1] as usize {
313            let other = groups[adj.clusters[i] as usize].group;
314            if other < 0 || acc[other as usize] == 0 {
315                continue;
316            }
317            let other = other as usize;
318            let shared = acc[other];
319            acc[other] = 0;
320            if groups[id].size as usize + groups[other].size as usize > max {
321                continue;
322            }
323            let mut sc =
324                shared as i32 as f32 * (r + 1. / ctx.sqrt(groups[other].vertices as i32 as f32));
325            if bounds {
326                sc *= 1. + 0.4 * score(groups[id], groups[other], ctx)?;
327            }
328            finite(sc)?;
329            if sc > bestscore {
330                best = Some((other, shared));
331                bestscore = sc;
332            }
333        }
334        ci = groups[c].next;
335    }
336    Ok(best)
337}
338#[inline(always)]
339fn checked<const CHECK: bool>(x: f32) -> Result<f32, Error> {
340    if CHECK {
341        finite(x)
342    } else {
343        Ok(x)
344    }
345}
346// ClusterGeneric centroid and squared radius, in upstream operation order.
347#[inline(always)]
348fn group_sphere<const CHECK: bool>(
349    p: Positions<'_>,
350    verts: &[u32],
351) -> Result<([f32; 3], f32), Error> {
352    let mut center = [0f32; 3];
353    for &v in verts {
354        let pp = point(p, v);
355        for (k, &x) in pp.iter().enumerate() {
356            center[k] = checked::<CHECK>(center[k] + x)?;
357        }
358    }
359    for x in &mut center {
360        *x /= verts.len() as f32;
361    }
362    let mut r = 0.;
363    for &v in verts {
364        let dp = sub(point(p, v), center);
365        let d = checked::<CHECK>(dot(dp, dp))?;
366        if r < d {
367            r = d;
368        }
369    }
370    Ok((center, r))
371}
372fn partition(
373    out: &mut [u32],
374    indices: &[u32],
375    counts: &[u32],
376    vertices: usize,
377    p: Option<Positions<'_>>,
378    target: usize,
379    ctx: &mut Context<'_>,
380) -> Result<usize, Error> {
381    partition_weighted(out, indices, counts, None, vertices, p, target, ctx)
382}
383
384// Internal indivisible regions can represent several clusters. The public
385// partitioner retains unit weights and its original ordering and work charges.
386#[allow(clippy::too_many_arguments)]
387pub(crate) fn partition_weighted(
388    out: &mut [u32],
389    indices: &[u32],
390    counts: &[u32],
391    weights: Option<&[u32]>,
392    vertices: usize,
393    p: Option<Positions<'_>>,
394    target: usize,
395    ctx: &mut Context<'_>,
396) -> Result<usize, Error> {
397    if target == 0 {
398        return Err(Error::InvalidParameter);
399    }
400    let max = target.checked_add(target / 3).ok_or(Error::SizeOverflow)?;
401    let n = counts.len();
402    if let Some(weights) = weights {
403        if weights.len() != n || weights.contains(&0) {
404            return Err(Error::InvalidLayout);
405        }
406        ctx.tick(weights.len())?;
407        weights.iter().try_fold(0u32, |sum, &w| {
408            sum.checked_add(w).ok_or(Error::SizeOverflow)
409        })?;
410    }
411    ctx.large_memo();
412    if n > i32::MAX as usize || vertices > u32::MAX as usize || indices.len() > u32::MAX as usize {
413        return Err(Error::SizeOverflow);
414    }
415    ctx.tick(counts.len() + indices.len())?;
416    let mut sum = 0usize;
417    for &n in counts {
418        if n == 0 {
419            return Err(Error::InvalidParameter);
420        }
421        sum = sum.checked_add(n as usize).ok_or(Error::SizeOverflow)?;
422    }
423    if sum != indices.len() {
424        return Err(Error::InvalidLayout);
425    }
426    if indices.iter().any(|&v| v as usize >= vertices) {
427        return Err(Error::IndexOutOfBounds);
428    }
429    if let Some(p) = p {
430        if p.len() != vertices {
431            return Err(Error::InvalidLayout);
432        }
433        ctx.positions(p)?;
434    }
435    let mut used = ctx.alloc::<u8>(vertices)?;
436    let mut filtered = ctx.alloc::<u32>(indices.len())?;
437    let mut offsets = ctx.alloc::<u32>(n + 1)?;
438    let (mut start, mut write) = (0, 0);
439    // Reuse the existing byte table as a generation map on dense inputs.
440    // This avoids clearing the unique vertex list after every cluster. Sparse
441    // inputs retain the old local clear, so a wide unused vertex range is never
442    // repeatedly scanned. Storage and the exact visit charges are unchanged.
443    let tagged = vertices <= indices.len() / 3;
444    let mut generation_start = 0;
445    for (i, &count) in counts.iter().enumerate() {
446        offsets[i] = write as u32;
447        ctx.tick(count as usize)?;
448        let tag = if tagged { (i % 255 + 1) as u8 } else { 1 };
449        if tagged && tag == 1 && i != 0 {
450            // Never scan more entries than this generation actually touched.
451            // A whole-table clear on every wrap would otherwise be quadratic
452            // for many small clusters over a large vertex domain.
453            let touched = &filtered[generation_start..write];
454            if used.len() <= touched.len() {
455                used.fill(0);
456            } else {
457                for &v in touched {
458                    used[v as usize] = 0;
459                }
460            }
461            generation_start = write;
462        }
463        for &v in &indices[start..start + count as usize] {
464            if used[v as usize] != tag {
465                filtered[write] = v;
466                write += 1;
467                used[v as usize] = tag;
468            }
469        }
470        if !tagged && i + 1 < n {
471            for &v in &filtered[offsets[i] as usize..write] {
472                used[v as usize] = 0;
473            }
474        }
475        start += count as usize;
476    }
477    offsets[n] = write as u32;
478    filtered.truncate(write);
479    let adj = adjacent(&filtered, &offsets, n, vertices, ctx)?;
480    let mut groups = ctx.alloc::<Group>(n)?;
481    let mut heap = ctx.alloc::<Order>(n)?;
482    let mut acc = ctx.alloc(n)?;
483    let mut pending = 0;
484    for i in 0..n {
485        let verts = &filtered[offsets[i] as usize..offsets[i + 1] as usize];
486        let mut g = Group {
487            group: i as i32,
488            next: -1,
489            size: weights.map_or(1, |w| w[i]),
490            vertices: verts.len() as u32,
491            ..Group::default()
492        };
493        if let Some(p) = p {
494            ctx.tick(verts.len() * 2)?;
495            // Moderate coordinates (|x| <= 1e8) bound every partial sum by
496            // 1e8 * 2^32 and every squared offset by 3 * (2e8)^2, so these
497            // finiteness checks cannot fail there (as in the meshlet modules).
498            let (center, r) = if ctx.moderate {
499                group_sphere::<false>(p, verts)?
500            } else {
501                group_sphere::<true>(p, verts)?
502            };
503            g.center = center;
504            g.radius = ctx.sqrt(r);
505        }
506        groups[i] = g;
507        push(
508            &mut heap,
509            &mut pending,
510            Order {
511                id: i as u32,
512                order: g.vertices as i32,
513            },
514        );
515    }
516    while pending != 0 {
517        ctx.tick(1)?;
518        let mut top = pop(&mut heap, &mut pending);
519        let id = top.id as usize;
520        if groups[id].size == 0 {
521            continue;
522        }
523        let mut ci = id as i32;
524        while ci >= 0 {
525            ctx.tick(1)?;
526            groups[ci as usize].group = -1;
527            ci = groups[ci as usize].next;
528        }
529        if groups[id].size as usize >= target {
530            continue;
531        }
532        let Some((best, shared)) = pick(&groups, id, &adj, max, p.is_some(), &mut acc, ctx)? else {
533            continue;
534        };
535        let mut tail = id;
536        while groups[tail].next >= 0 {
537            ctx.tick(1)?;
538            tail = groups[tail].next as usize;
539        }
540        groups[tail].next = best as i32;
541        groups[id].size += groups[best].size;
542        let vertices = groups[id]
543            .vertices
544            .checked_add(groups[best].vertices)
545            .ok_or(Error::SizeOverflow)?;
546        groups[id].vertices = if vertices > shared {
547            vertices - shared
548        } else {
549            1
550        };
551        groups[best].size = 0;
552        groups[best].vertices = 0;
553        if p.is_some() {
554            let b = groups[best];
555            merge(&mut groups[id], b, ctx)?;
556            groups[best].radius = 0.;
557        }
558        ci = id as i32;
559        while ci >= 0 {
560            ctx.tick(1)?;
561            groups[ci as usize].group = id as i32;
562            ci = groups[ci as usize].next;
563        }
564        top.order = groups[id].vertices as i32;
565        push(&mut heap, &mut pending, top);
566    }
567    if p.is_some() {
568        let mut order = ctx.alloc::<u32>(n)?;
569        let mut count = 0;
570        for (i, g) in groups.iter().enumerate() {
571            if g.size != 0 {
572                order[count] = i as u32;
573                count += 1;
574            }
575        }
576        spatial(&mut groups, &mut order[..count], target, max, 0, ctx)?;
577    }
578    let mut next = 0;
579    for i in 0..n {
580        if groups[i].size == 0 {
581            continue;
582        }
583        let mut j = i as i32;
584        while j >= 0 {
585            ctx.tick(1)?;
586            out[j as usize] = next as u32;
587            j = groups[j as usize].next;
588        }
589        next += 1;
590    }
591    Ok(next)
592}
593/// `meshopt_partitionClusters`. Clusters may contain arbitrary index lists; empty clusters are invalid.
594/// Positions are optional; without them only connected clusters merge.
595///
596/// # Errors
597/// `InvalidLayout` for inconsistent counts/positions; `InvalidParameter` for empty clusters or an invalid target;
598/// `IndexOutOfBounds` for invalid references; `NumericalFailure` for non-finite geometry or calculations.
599/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
600#[inline]
601pub fn partition_clusters_generic<I: crate::Index>(
602    indices: &[I],
603    counts: &[u32],
604    vertex_count: usize,
605    p: Option<Positions<'_>>,
606    target: usize,
607    workspace: &mut Workspace,
608) -> Result<Partitions, Error> {
609    I::with_input(indices, workspace, |indices, workspace| {
610        partition_clusters_u32(indices, counts, vertex_count, p, target, workspace)
611    })
612}
613
614fn partition_clusters_u32(
615    indices: &[u32],
616    counts: &[u32],
617    vertex_count: usize,
618    p: Option<Positions<'_>>,
619    target: usize,
620    workspace: &mut Workspace,
621) -> Result<Partitions, Error> {
622    let mut ctx = Context::new(workspace)?;
623    let mut assignments = ctx.alloc(counts.len())?;
624    let count = partition(
625        &mut assignments,
626        indices,
627        counts,
628        vertex_count,
629        p,
630        target,
631        &mut ctx,
632    )?;
633    Ok(Partitions { assignments, count })
634}
635/// Caller-buffer cluster partitioning; a late failure may modify the used prefix.
636///
637/// # Errors
638/// Same errors as [`partition_clusters`]. `BufferTooSmall` if the assignments buffer is too short.
639#[inline]
640pub fn partition_clusters_into_generic<I: crate::Index>(
641    out: &mut [u32],
642    indices: &[I],
643    counts: &[u32],
644    vertex_count: usize,
645    p: Option<Positions<'_>>,
646    target: usize,
647    workspace: &mut Workspace,
648) -> Result<usize, Error> {
649    I::with_input(indices, workspace, |indices, workspace| {
650        partition_clusters_into_u32(out, indices, counts, vertex_count, p, target, workspace)
651    })
652}
653
654fn partition_clusters_into_u32(
655    out: &mut [u32],
656    indices: &[u32],
657    counts: &[u32],
658    vertex_count: usize,
659    p: Option<Positions<'_>>,
660    target: usize,
661    workspace: &mut Workspace,
662) -> Result<usize, Error> {
663    let mut ctx = Context::new(workspace)?;
664    if out.len() < counts.len() {
665        return Err(Error::BufferTooSmall);
666    }
667    partition(
668        &mut out[..counts.len()],
669        indices,
670        counts,
671        vertex_count,
672        p,
673        target,
674        &mut ctx,
675    )
676}
677
678/// The source-compatible u32 entry point; see [`partition_clusters_generic`] for selectable index widths.
679#[inline]
680pub fn partition_clusters(
681    indices: &[u32],
682    counts: &[u32],
683    vertex_count: usize,
684    p: Option<Positions<'_>>,
685    target: usize,
686    workspace: &mut Workspace,
687) -> Result<Partitions, Error> {
688    partition_clusters_generic::<u32>(indices, counts, vertex_count, p, target, workspace)
689}
690
691/// The source-compatible u32 entry point; see [`partition_clusters_into_generic`] for selectable index widths.
692#[inline]
693pub fn partition_clusters_into(
694    out: &mut [u32],
695    indices: &[u32],
696    counts: &[u32],
697    vertex_count: usize,
698    p: Option<Positions<'_>>,
699    target: usize,
700    workspace: &mut Workspace,
701) -> Result<usize, Error> {
702    partition_clusters_into_generic::<u32>(out, indices, counts, vertex_count, p, target, workspace)
703}
704
705#[cfg(test)]
706mod weighted_tests {
707    use super::*;
708
709    #[test]
710    fn indivisible_regions_charge_their_cluster_counts() {
711        let indices = [0, 1, 1, 2, 2, 3, 3, 4];
712        let counts = [2; 4];
713        let mut out = [0; 4];
714        let mut ws = Workspace::default();
715        let mut ctx = Context::new(&mut ws).expect("context");
716        let groups = partition_weighted(
717            &mut out,
718            &indices,
719            &counts,
720            Some(&[3; 4]),
721            5,
722            None,
723            4,
724            &mut ctx,
725        )
726        .expect("weighted partition");
727        // The maximum is five clusters: two three-cluster regions cannot merge.
728        assert_eq!(groups, 4);
729        let groups =
730            partition(&mut out, &indices, &counts, 5, None, 4, &mut ctx).expect("unit partition");
731        assert_eq!(groups, 1);
732        assert_eq!(out, [0; 4]);
733        assert_eq!(
734            partition_weighted(
735                &mut out,
736                &indices,
737                &counts,
738                Some(&[u32::MAX; 4]),
739                5,
740                None,
741                4,
742                &mut ctx,
743            ),
744            Err(Error::SizeOverflow)
745        );
746    }
747}