From 82a46ea6f8829fc40205d0d3cabf4017eb738d9a Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Tue, 30 Aug 2022 11:08:27 -0500 Subject: Geometry Nodes: Use separate field context for each geometry type Using the same `GeometryComponentFieldContext` for all situations, even when only one geometry type is supported is misleading, and mixes too many different abstraction levels into code that could be simpler. With the attribute API moved out of geometry components recently, the "component" system is just getting in the way here. This commit adds specific field contexts for geometry types: meshes, curves, point clouds, and instances. There are also separate field input helper classes, to help reduce boilerplate for fields that only support specific geometry types. Another benefit of this change is that it separates geometry components from fields, which makes it easier to see the purpose of the two concepts, and how they relate. Because we want to be able to evaluate a field on just `CurvesGeometry` rather than the full `Curves` data-block, the generic "geometry context" had to be changed to avoid using `GeometryComponent`, since there is no corresponding geometry component type. The resulting void pointer is ugly, but only turns up in three places in practice. When Apple clang supports `std::variant`, that could be used instead. Differential Revision: https://developer.blender.org/D15519 --- source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc') diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc index 0932de237a9..443f67be421 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc @@ -504,19 +504,17 @@ static void geometry_set_curve_trim(GeometrySet &geometry_set, if (!geometry_set.has_curves()) { return; } + const Curves &src_curves_id = *geometry_set.get_curves_for_read(); + const bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); - CurveComponent &component = geometry_set.get_component_for_write(); - GeometryComponentFieldContext field_context{component, ATTR_DOMAIN_CURVE}; - const int domain_size = component.attribute_domain_size(ATTR_DOMAIN_CURVE); - - fn::FieldEvaluator evaluator{field_context, domain_size}; + bke::CurvesFieldContext field_context{curves, ATTR_DOMAIN_CURVE}; + fn::FieldEvaluator evaluator{field_context, curves.curves_num()}; evaluator.add(start_field); evaluator.add(end_field); evaluator.evaluate(); const VArray starts = evaluator.get_evaluated(0); const VArray ends = evaluator.get_evaluated(1); - const Curves &src_curves_id = *geometry_set.get_curves_for_read(); std::unique_ptr curve = curves_to_curve_eval(src_curves_id); MutableSpan splines = curve->splines(); -- cgit v1.2.3 From eaf416693dcb431ec122fc559788e6c930038c23 Mon Sep 17 00:00:00 2001 From: Mattias Fredriksson Date: Tue, 13 Sep 2022 11:36:14 -0500 Subject: Geometry Nodes: Port the trim curve node to the new data-block The trim functionality is implemented in the geometry module, and generalized a bit to be potentially useful for bisecting in the future. The implementation is based on a helper type called `IndexRangeCyclic` which allows iteration over all control points between two points on a curve. Catmull Rom curves are now supported-- trimmed without resampling first. However, maintaining the exact shape is not possible. NURBS splines are still converted to polylines using the evaluated curve concept. Performance is equivalent or faster then a 3.1 build with regards to node timings. Compared to 3.3 and 3.2, it's easy to observe test cases where the node is at least 3 or 4 times faster. Differential Revision: https://developer.blender.org/D14481 --- .../nodes/geometry/nodes/node_geo_curve_trim.cc | 477 ++------------------- 1 file changed, 35 insertions(+), 442 deletions(-) (limited to 'source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc') diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc index 443f67be421..0d3ae47e712 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc @@ -9,12 +9,12 @@ #include "NOD_socket_search_link.hh" +#include "GEO_trim_curves.hh" + #include "node_geometry_util.hh" namespace blender::nodes::node_geo_curve_trim_cc { -using blender::attribute_math::mix2; - NODE_STORAGE_FUNCS(NodeGeometryCurveTrim) static void node_declare(NodeDeclarationBuilder &b) @@ -108,394 +108,6 @@ static void node_gather_link_searches(GatherLinkSearchOpParams ¶ms) } } -struct TrimLocation { - /* Control point index at the start side of the trim location. */ - int left_index; - /* Control point index at the end of the trim location's segment. */ - int right_index; - /* The factor between the left and right indices. */ - float factor; -}; - -template -static void shift_slice_to_start(MutableSpan data, const int start_index, const int num) -{ - BLI_assert(start_index + num - 1 <= data.size()); - memmove(data.data(), &data[start_index], sizeof(T) * num); -} - -/* Shift slice to start of span and modifies start and end data. */ -template -static void linear_trim_data(const TrimLocation &start, - const TrimLocation &end, - MutableSpan data) -{ - const int num = end.right_index - start.left_index + 1; - - if (start.left_index > 0) { - shift_slice_to_start(data, start.left_index, num); - } - - const T start_data = mix2(start.factor, data.first(), data[1]); - const T end_data = mix2(end.factor, data[num - 2], data[num - 1]); - - data.first() = start_data; - data[num - 1] = end_data; -} - -/** - * Identical operation as #linear_trim_data, but copy data to a new #MutableSpan rather than - * modifying the original data. - */ -template -static void linear_trim_to_output_data(const TrimLocation &start, - const TrimLocation &end, - Span src, - MutableSpan dst) -{ - const int num = end.right_index - start.left_index + 1; - - const T start_data = mix2(start.factor, src[start.left_index], src[start.right_index]); - const T end_data = mix2(end.factor, src[end.left_index], src[end.right_index]); - - dst.copy_from(src.slice(start.left_index, num)); - dst.first() = start_data; - dst.last() = end_data; -} - -/* Look up the control points to the left and right of factor, and get the factor between them. */ -static TrimLocation lookup_control_point_position(const Spline::LookupResult &lookup, - const BezierSpline &spline) -{ - Span offsets = spline.control_point_offsets(); - - const int *offset = std::lower_bound(offsets.begin(), offsets.end(), lookup.evaluated_index); - const int index = offset - offsets.begin(); - - const int left = offsets[index] > lookup.evaluated_index ? index - 1 : index; - const int right = left == (spline.size() - 1) ? 0 : left + 1; - - const float offset_in_segment = lookup.evaluated_index + lookup.factor - offsets[left]; - const int segment_eval_num = offsets[left + 1] - offsets[left]; - const float factor = std::clamp(offset_in_segment / segment_eval_num, 0.0f, 1.0f); - - return {left, right, factor}; -} - -static void trim_poly_spline(Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - /* Poly splines have a 1 to 1 mapping between control points and evaluated points. */ - const TrimLocation start = { - start_lookup.evaluated_index, start_lookup.next_evaluated_index, start_lookup.factor}; - const TrimLocation end = { - end_lookup.evaluated_index, end_lookup.next_evaluated_index, end_lookup.factor}; - - const int num = end.right_index - start.left_index + 1; - - linear_trim_data(start, end, spline.positions()); - linear_trim_data(start, end, spline.radii()); - linear_trim_data(start, end, spline.tilts()); - - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional src = spline.attributes.get_for_write(attribute_id); - BLI_assert(src); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - linear_trim_data(start, end, src->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - spline.resize(num); -} - -/** - * Trim NURB splines by converting to a poly spline. - */ -static PolySpline trim_nurbs_spline(const Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - /* Since this outputs a poly spline, the evaluated indices are the control point indices. */ - const TrimLocation start = { - start_lookup.evaluated_index, start_lookup.next_evaluated_index, start_lookup.factor}; - const TrimLocation end = { - end_lookup.evaluated_index, end_lookup.next_evaluated_index, end_lookup.factor}; - - const int num = end.right_index - start.left_index + 1; - - /* Create poly spline and copy trimmed data to it. */ - PolySpline new_spline; - new_spline.resize(num); - - /* Copy generic attribute data. */ - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - std::optional src = spline.attributes.get_for_read(attribute_id); - BLI_assert(src); - if (!new_spline.attributes.create(attribute_id, meta_data.data_type)) { - BLI_assert_unreachable(); - return false; - } - std::optional dst = new_spline.attributes.get_for_write(attribute_id); - BLI_assert(dst); - - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - VArray eval_data = spline.interpolate_to_evaluated(src->typed()); - linear_trim_to_output_data( - start, end, eval_data.get_internal_span(), dst->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - linear_trim_to_output_data( - start, end, spline.evaluated_positions(), new_spline.positions()); - - VArray evaluated_radii = spline.interpolate_to_evaluated(spline.radii()); - linear_trim_to_output_data( - start, end, evaluated_radii.get_internal_span(), new_spline.radii()); - - VArray evaluated_tilts = spline.interpolate_to_evaluated(spline.tilts()); - linear_trim_to_output_data( - start, end, evaluated_tilts.get_internal_span(), new_spline.tilts()); - - return new_spline; -} - -/** - * Trim Bezier splines by adjusting the first and last handles - * and control points to maintain the original shape. - */ -static void trim_bezier_spline(Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - BezierSpline &bezier_spline = static_cast(spline); - - const TrimLocation start = lookup_control_point_position(start_lookup, bezier_spline); - TrimLocation end = lookup_control_point_position(end_lookup, bezier_spline); - - const Span control_offsets = bezier_spline.control_point_offsets(); - - /* The number of control points in the resulting spline. */ - const int num = end.right_index - start.left_index + 1; - - /* Trim the spline attributes. Done before end.factor recalculation as it needs - * the original end.factor value. */ - linear_trim_data(start, end, bezier_spline.radii()); - linear_trim_data(start, end, bezier_spline.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional src = spline.attributes.get_for_write(attribute_id); - BLI_assert(src); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - linear_trim_data(start, end, src->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - /* Recalculate end.factor if the `num` is two, because the adjustment in the - * position of the control point of the spline to the left of the new end point will change the - * factor between them. */ - if (num == 2) { - if (start_lookup.factor == 1.0f) { - end.factor = 0.0f; - } - else { - end.factor = (end_lookup.evaluated_index + end_lookup.factor - - (start_lookup.evaluated_index + start_lookup.factor)) / - (control_offsets[end.right_index] - - (start_lookup.evaluated_index + start_lookup.factor)); - end.factor = std::clamp(end.factor, 0.0f, 1.0f); - } - } - - BezierSpline::InsertResult start_point = bezier_spline.calculate_segment_insertion( - start.left_index, start.right_index, start.factor); - - /* Update the start control point parameters so they are used calculating the new end point. */ - bezier_spline.positions()[start.left_index] = start_point.position; - bezier_spline.handle_positions_right()[start.left_index] = start_point.right_handle; - bezier_spline.handle_positions_left()[start.right_index] = start_point.handle_next; - - const BezierSpline::InsertResult end_point = bezier_spline.calculate_segment_insertion( - end.left_index, end.right_index, end.factor); - - /* If `num` is two, then the start point right handle needs to change to reflect the end point - * previous handle update. */ - if (num == 2) { - start_point.right_handle = end_point.handle_prev; - } - - /* Shift control point position data to start at beginning of array. */ - if (start.left_index > 0) { - shift_slice_to_start(bezier_spline.positions(), start.left_index, num); - shift_slice_to_start(bezier_spline.handle_positions_left(), start.left_index, num); - shift_slice_to_start(bezier_spline.handle_positions_right(), start.left_index, num); - } - - bezier_spline.positions().first() = start_point.position; - bezier_spline.positions()[num - 1] = end_point.position; - - bezier_spline.handle_positions_left().first() = start_point.left_handle; - bezier_spline.handle_positions_left()[num - 1] = end_point.left_handle; - - bezier_spline.handle_positions_right().first() = start_point.right_handle; - bezier_spline.handle_positions_right()[num - 1] = end_point.right_handle; - - /* If there is at least one control point between the endpoints, update the control - * point handle to the right of the start point and to the left of the end point. */ - if (num > 2) { - bezier_spline.handle_positions_left()[start.right_index - start.left_index] = - start_point.handle_next; - bezier_spline.handle_positions_right()[end.left_index - start.left_index] = - end_point.handle_prev; - } - - bezier_spline.resize(num); -} - -static void trim_spline(SplinePtr &spline, - const Spline::LookupResult start, - const Spline::LookupResult end) -{ - switch (spline->type()) { - case CURVE_TYPE_BEZIER: - trim_bezier_spline(*spline, start, end); - break; - case CURVE_TYPE_POLY: - trim_poly_spline(*spline, start, end); - break; - case CURVE_TYPE_NURBS: - spline = std::make_unique(trim_nurbs_spline(*spline, start, end)); - break; - case CURVE_TYPE_CATMULL_ROM: - BLI_assert_unreachable(); - spline = {}; - } - spline->mark_cache_invalid(); -} - -template -static void to_single_point_data(const TrimLocation &trim, MutableSpan data) -{ - data.first() = mix2(trim.factor, data[trim.left_index], data[trim.right_index]); -} -template -static void to_single_point_data(const TrimLocation &trim, Span src, MutableSpan dst) -{ - dst.first() = mix2(trim.factor, src[trim.left_index], src[trim.right_index]); -} - -static void to_single_point_bezier(Spline &spline, const Spline::LookupResult &lookup) -{ - BezierSpline &bezier = static_cast(spline); - - const TrimLocation trim = lookup_control_point_position(lookup, bezier); - - const BezierSpline::InsertResult new_point = bezier.calculate_segment_insertion( - trim.left_index, trim.right_index, trim.factor); - bezier.positions().first() = new_point.position; - bezier.handle_types_left().first() = BEZIER_HANDLE_FREE; - bezier.handle_types_right().first() = BEZIER_HANDLE_FREE; - bezier.handle_positions_left().first() = new_point.left_handle; - bezier.handle_positions_right().first() = new_point.right_handle; - - to_single_point_data(trim, bezier.radii()); - to_single_point_data(trim, bezier.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional data = spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(data->type(), [&](auto dummy) { - using T = decltype(dummy); - to_single_point_data(trim, data->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - spline.resize(1); -} - -static void to_single_point_poly(Spline &spline, const Spline::LookupResult &lookup) -{ - const TrimLocation trim{lookup.evaluated_index, lookup.next_evaluated_index, lookup.factor}; - - to_single_point_data(trim, spline.positions()); - to_single_point_data(trim, spline.radii()); - to_single_point_data(trim, spline.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional data = spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(data->type(), [&](auto dummy) { - using T = decltype(dummy); - to_single_point_data(trim, data->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - spline.resize(1); -} - -static PolySpline to_single_point_nurbs(const Spline &spline, const Spline::LookupResult &lookup) -{ - /* Since this outputs a poly spline, the evaluated indices are the control point indices. */ - const TrimLocation trim{lookup.evaluated_index, lookup.next_evaluated_index, lookup.factor}; - - /* Create poly spline and copy trimmed data to it. */ - PolySpline new_spline; - new_spline.resize(1); - - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - new_spline.attributes.create(attribute_id, meta_data.data_type); - std::optional src = spline.attributes.get_for_read(attribute_id); - std::optional dst = new_spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - VArray eval_data = spline.interpolate_to_evaluated(src->typed()); - to_single_point_data(trim, eval_data.get_internal_span(), dst->typed()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - to_single_point_data(trim, spline.evaluated_positions(), new_spline.positions()); - - VArray evaluated_radii = spline.interpolate_to_evaluated(spline.radii()); - to_single_point_data(trim, evaluated_radii.get_internal_span(), new_spline.radii()); - - VArray evaluated_tilts = spline.interpolate_to_evaluated(spline.tilts()); - to_single_point_data(trim, evaluated_tilts.get_internal_span(), new_spline.tilts()); - - return new_spline; -} - -static void to_single_point_spline(SplinePtr &spline, const Spline::LookupResult &lookup) -{ - switch (spline->type()) { - case CURVE_TYPE_BEZIER: - to_single_point_bezier(*spline, lookup); - break; - case CURVE_TYPE_POLY: - to_single_point_poly(*spline, lookup); - break; - case CURVE_TYPE_NURBS: - spline = std::make_unique(to_single_point_nurbs(*spline, lookup)); - break; - case CURVE_TYPE_CATMULL_ROM: - BLI_assert_unreachable(); - spline = {}; - } -} - static void geometry_set_curve_trim(GeometrySet &geometry_set, const GeometryNodeCurveSampleMode mode, Field &start_field, @@ -505,68 +117,49 @@ static void geometry_set_curve_trim(GeometrySet &geometry_set, return; } const Curves &src_curves_id = *geometry_set.get_curves_for_read(); - const bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); + const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); + if (src_curves.curves_num() == 0) { + return; + } - bke::CurvesFieldContext field_context{curves, ATTR_DOMAIN_CURVE}; - fn::FieldEvaluator evaluator{field_context, curves.curves_num()}; + bke::CurvesFieldContext field_context{src_curves, ATTR_DOMAIN_CURVE}; + fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; evaluator.add(start_field); evaluator.add(end_field); evaluator.evaluate(); const VArray starts = evaluator.get_evaluated(0); const VArray ends = evaluator.get_evaluated(1); - std::unique_ptr curve = curves_to_curve_eval(src_curves_id); - MutableSpan splines = curve->splines(); - - threading::parallel_for(splines.index_range(), 128, [&](IndexRange range) { - for (const int i : range) { - SplinePtr &spline = splines[i]; - - /* Currently trimming cyclic splines is not supported. It could be in the future though. */ - if (spline->is_cyclic()) { - continue; - } - - if (spline->evaluated_edges_num() == 0) { - continue; - } - - const float length = spline->length(); - if (length == 0.0f) { - continue; - } - - const float start = starts[i]; - const float end = ends[i]; - - /* When the start and end samples are reversed, instead of implicitly reversing the spline - * or switching the parameters, create a single point spline with the end sample point. */ - if (end <= start) { - if (mode == GEO_NODE_CURVE_SAMPLE_LENGTH) { - to_single_point_spline(spline, - spline->lookup_evaluated_length(std::clamp(start, 0.0f, length))); - } - else { - to_single_point_spline(spline, - spline->lookup_evaluated_factor(std::clamp(start, 0.0f, 1.0f))); - } - continue; - } - - if (mode == GEO_NODE_CURVE_SAMPLE_LENGTH) { - trim_spline(spline, - spline->lookup_evaluated_length(std::clamp(start, 0.0f, length)), - spline->lookup_evaluated_length(std::clamp(end, 0.0f, length))); - } - else { - trim_spline(spline, - spline->lookup_evaluated_factor(std::clamp(start, 0.0f, 1.0f)), - spline->lookup_evaluated_factor(std::clamp(end, 0.0f, 1.0f))); - } + const VArray cyclic = src_curves.cyclic(); + + /* If node length input is on form [0, 1] instead of [0, length]*/ + const bool normalized_length_lookup = mode == GEO_NODE_CURVE_SAMPLE_FACTOR; + + /* Stack start + end field. */ + Vector length_factors(src_curves.curves_num() * 2); + Vector lookup_indices(src_curves.curves_num() * 2); + threading::parallel_for(src_curves.curves_range(), 512, [&](IndexRange curve_range) { + for (const int64_t curve_i : curve_range) { + const bool negative_trim = !cyclic[curve_i] && starts[curve_i] > ends[curve_i]; + length_factors[curve_i] = starts[curve_i]; + length_factors[curve_i + src_curves.curves_num()] = negative_trim ? starts[curve_i] : + ends[curve_i]; + lookup_indices[curve_i] = curve_i; + lookup_indices[curve_i + src_curves.curves_num()] = curve_i; } }); - Curves *dst_curves_id = curve_eval_to_curves(*curve); + /* Create curve trim lookup table. */ + Array point_lookups = geometry::lookup_curve_points( + src_curves, length_factors, lookup_indices, normalized_length_lookup); + + bke::CurvesGeometry dst_curves = geometry::trim_curves( + src_curves, + src_curves.curves_range().as_span(), + point_lookups.as_span().slice(0, src_curves.curves_num()), + point_lookups.as_span().slice(src_curves.curves_num(), src_curves.curves_num())); + + Curves *dst_curves_id = bke::curves_new_nomain(std::move(dst_curves)); bke::curves_copy_parameters(src_curves_id, *dst_curves_id); geometry_set.replace_curves(dst_curves_id); } -- cgit v1.2.3 From ecf3435362cf2c1823b94a154c3f32a0c3412f53 Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Sun, 18 Sep 2022 15:10:04 -0500 Subject: Curves: Remove CurveEval and old Spline types `CurveEval` was added for the first iteration of geometry nodes curve support. Since then, it has been replaced by the new `Curves` type which is designed to be much faster for many curves and better integrated with the rest of Blender. Now that all curve nodes have been moved to use `Curves` (T95443), the type can be removed, along with the corresponding geometry component. --- source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc | 1 - 1 file changed, 1 deletion(-) (limited to 'source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc') diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc index 0d3ae47e712..1576b573058 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc @@ -1,7 +1,6 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ #include "BKE_curves.hh" -#include "BKE_spline.hh" #include "BLI_task.hh" #include "UI_interface.h" -- cgit v1.2.3