From e0c254c4445696f4e88690a2d35da1e3a760867e Mon Sep 17 00:00:00 2001 From: cilix42 Date: Sun, 26 Aug 2007 17:16:03 +0000 Subject: [PATCH] Rewrite of z-order code for 3D boxes, first stage (hopefully this is finally the right approach) --- src/axis-manip.cpp | 2 +- src/axis-manip.h | 17 ++- src/box3d-context.cpp | 4 +- src/box3d.cpp | 249 +++++++++++++++++++++++++++++++++++++++++- src/box3d.h | 7 +- src/line-geometry.cpp | 9 +- src/object-edit.cpp | 11 +- src/perspective3d.cpp | 2 +- 8 files changed, 285 insertions(+), 16 deletions(-) diff --git a/src/axis-manip.cpp b/src/axis-manip.cpp index c2edbfb89..7539f2324 100644 --- a/src/axis-manip.cpp +++ b/src/axis-manip.cpp @@ -22,7 +22,7 @@ FrontOrRear face_positions [2] = { FRONT, REAR }; std::pair get_remaining_axes (Axis axis) { if (!is_single_axis_direction (axis)) return std::make_pair (NONE, NONE); - Axis plane = orth_plane (axis); + Axis plane = orth_plane_or_axis (axis); return std::make_pair (extract_first_axis_direction (plane), extract_second_axis_direction (plane)); } diff --git a/src/axis-manip.h b/src/axis-manip.h index 027d17ea5..32c1e6137 100644 --- a/src/axis-manip.h +++ b/src/axis-manip.h @@ -72,12 +72,25 @@ inline guint opposite_face (guint face_id) { return face_id + ((face_id % 2 == 0) ? 1 : -1); } +inline guint number_of_axis_directions (Box3D::Axis axis) { + guint num = 0; + if (axis & Box3D::X) num++; + if (axis & Box3D::Y) num++; + if (axis & Box3D::Z) num++; + + return num; +} + +inline bool is_plane (Box3D::Axis plane) { + return (number_of_axis_directions (plane) == 2); +} + inline bool is_single_axis_direction (Box3D::Axis dir) { // tests whether dir is nonzero and a power of 2 return (!(dir & (dir - 1)) && dir); } -// Warning: We don't check that axis really unamiguously specifies a plane. +// Warning: We don't check that axis really unambiguously specifies a plane. // Make sure this is the case when calling this function. inline guint face_containing_corner (Box3D::Axis axis, guint corner) { if (!is_single_axis_direction (axis)) { @@ -109,7 +122,7 @@ inline Box3D::Axis extract_second_axis_direction (Box3D::Axis dirs) { return extract_first_axis_direction ((Box3D::Axis) (dirs ^ extract_first_axis_direction(dirs))); } -inline Box3D::Axis orth_plane (Box3D::Axis axis) { +inline Box3D::Axis orth_plane_or_axis (Box3D::Axis axis) { return (Box3D::Axis) (Box3D::XYZ ^ axis); } diff --git a/src/box3d-context.cpp b/src/box3d-context.cpp index 8ef5f5960..f5a76655c 100644 --- a/src/box3d-context.cpp +++ b/src/box3d-context.cpp @@ -592,7 +592,7 @@ static void sp_3dbox_drag(SP3DBoxContext &bc, guint state) SP_3DBOX (bc.item)->faces[5]->set_style (NULL, false); bc.item->updateRepr(); - sp_3dbox_set_z_orders (SP_3DBOX (bc.item)); + sp_3dbox_set_z_orders_in_the_first_place (SP_3DBOX (bc.item)); // TODO: It would be nice to show the VPs during dragging, but since there is no selection // at this point (only after finishing the box), we must do this "manually" @@ -616,7 +616,7 @@ static void sp_3dbox_drag(SP3DBoxContext &bc, guint state) NR::Point origin_w(ec->xp, ec->yp); NR::Point origin(desktop->w2d(origin_w)); sp_3dbox_position_set(bc); - sp_3dbox_set_z_orders (SP_3DBOX (bc.item)); + sp_3dbox_set_z_orders_in_the_first_place (SP_3DBOX (bc.item)); // status text //GString *Ax = SP_PX_TO_METRIC_STRING(origin[NR::X], desktop->namedview->getDefaultMetric()); diff --git a/src/box3d.cpp b/src/box3d.cpp index f822a1b20..0f672aab2 100644 --- a/src/box3d.cpp +++ b/src/box3d.cpp @@ -497,7 +497,241 @@ bool sp_3dbox_recompute_z_orders (SP3DBox *box) return false; } -void sp_3dbox_set_z_orders (SP3DBox *box) +// convenience +static bool sp_3dbox_is_subset_or_superset (std::vector const &list1, std::vector const &list2) +{ + return (std::includes (list1.begin(), list1.end(), list2.begin(), list2.end()) || + std::includes (list2.begin(), list2.end(), list1.begin(), list1.end())); +} + +static bool sp_3dbox_differ_by_opposite_faces (std::vector const &list1, std::vector const &list2) +{ + std::vector diff1; + std::vector diff2; + std::set_difference (list1.begin(), list1.end(), list2.begin(), list2.end(), + std::insert_iterator >(diff1, diff1.begin())); + std::set_difference (list2.begin(), list2.end(), list1.begin(), list1.end(), + std::insert_iterator >(diff2, diff2.begin())); + + if (diff1.size() == 3 || diff1.size() != diff2.size()) + return false; + + for (guint i = 0; i < diff1.size(); ++i) { + if (std::find (diff2.begin(), diff2.end(), Box3D::opposite_face (diff1[i])) == diff2.end()) { + return false; + } + } + return true; +} + +static gint +sp_3dbox_face_containing_diagonal_corners (guint corner1, guint corner2) +{ + Box3D::Axis plane = (Box3D::Axis) (corner1 ^ corner2); + if (!Box3D::is_plane (plane)) { + g_warning ("Corners %d and %d should span a plane.\n", corner1, corner2); + return 0; + } + + return Box3D::face_containing_corner (plane, corner1); +} + +static std::vector sp_3dbox_adjacent_faces_of_edge (guint corner1, guint corner2) { + std::vector adj_faces; + Box3D::Axis edge = (Box3D::Axis) (corner1 ^ corner2); + if (!Box3D::is_single_axis_direction (edge)) { + return adj_faces; + } + + Box3D::Axis plane = Box3D::orth_plane_or_axis (edge); + Box3D::Axis axis1 = Box3D::extract_first_axis_direction (plane); + Box3D::Axis axis2 = Box3D::extract_second_axis_direction (plane); + adj_faces.push_back (Box3D::face_containing_corner ((Box3D::Axis) (edge ^ axis1), corner1)); + adj_faces.push_back (Box3D::face_containing_corner ((Box3D::Axis) (edge ^ axis2), corner1)); + return adj_faces; +} + +static std::vector sp_3dbox_faces_meeting_in_corner (guint corner) { + std::vector faces; + for (int i = 0; i < 3; ++i) { + faces.push_back (sp_3dbox_face_containing_diagonal_corners (corner, corner ^ Box3D::planes[i])); + } + return faces; +} + +static void sp_3dbox_remaining_faces (std::vector const &faces, std::vector &rem_faces) +{ + rem_faces.clear(); + for (gint i = 0; i < 6; ++i) { + if (std::find (faces.begin(), faces.end(), i) == faces.end()) { + rem_faces.push_back (i); + } + } +} + +/* + * Given two adjacent edges (\a c2,\a c1) and (\a c2, \a c3) of \a box (with common corner \a c2), + * check whether both lie on the convex hull of the point configuration given by \a box's corners. + */ +static bool +sp_3dbox_is_border_edge_pair (SP3DBox *box, guint const c1, guint const c2, guint const c3) +{ + Box3D::Axis edge21 = (Box3D::Axis) (c2 ^ c1); + Box3D::Axis edge23 = (Box3D::Axis) (c2 ^ c3); + Box3D::Axis rear_axis = Box3D::orth_plane_or_axis ((Box3D::Axis) (edge21 ^ edge23)); + + NR::Point corner2 = box->corners[c2]; + NR::Point dir21 = box->corners[c1] - corner2; + NR::Point dir23 = box->corners[c3] - corner2; + + if (!Box3D::lies_in_sector (dir21, dir23, box->corners[c2 ^ edge21 ^ edge23] - corner2) || + !Box3D::lies_in_sector (dir21, dir23, box->corners[c2 ^ rear_axis] - corner2) || + !Box3D::lies_in_sector (dir21, dir23, box->corners[c2 ^ rear_axis ^ edge21] - corner2) || + !Box3D::lies_in_sector (dir21, dir23, box->corners[c2 ^ rear_axis ^ edge21 ^ edge23] - corner2) || + !Box3D::lies_in_sector (dir21, dir23, box->corners[c2 ^ rear_axis ^ edge23] - corner2)) { + // corner triple c1, c2, c3 doesn't bound the convex hull + return false; + } + // corner triple c1, c2, c3 bounds the convex hull + return true; +} + +/* + * Test whether there are any adjacent corners of \a corner (i.e., connected with it along one of the axes) + * such that the corresponding edges bound the convex hull of the box (as a point configuration in the plane) + * If this is the case, return the corresponding two adjacent corners; otherwise return (-1, -1). + */ +static Box3D::Axis +sp_3dbox_axis_pair_bounding_convex_hull (SP3DBox *box, guint corner) + { + guint adj1 = corner ^ Box3D::X; + guint adj2 = corner ^ Box3D::Y; + guint adj3 = corner ^ Box3D::Z; + + if (sp_3dbox_is_border_edge_pair (box, adj1, corner, adj2)) { + return Box3D::XY; + } + if (sp_3dbox_is_border_edge_pair (box, adj1, corner, adj3)) { + return Box3D::XZ; + } + if (sp_3dbox_is_border_edge_pair (box, adj2, corner, adj3)) { + return Box3D::YZ; + } + return Box3D::NONE; +} + +// inside_hull is modified 'in place' by the following function +static void sp_3dbox_corner_configuration (SP3DBox *box, std::vector &on_hull, std::vector &inside_hull) +{ + for (int i = 0; i < 8; ++i) { + Box3D::Axis bounding_edges = sp_3dbox_axis_pair_bounding_convex_hull (box, i); + if (bounding_edges != Box3D::NONE) { + on_hull.push_back (i); + } else { + inside_hull.push_back (i); + } + } +} + +/* returns true if there was a change in the z-orders (which triggers an update of the repr) */ +static bool sp_3dbox_recompute_z_orders_by_corner_configuration (SP3DBox *box) +{ + guint new_z_orders[6]; + Box3D::Axis front_rear_axis = Box3D::Z; + + Box3D::Axis axis1 = Box3D::get_remaining_axes (front_rear_axis).first; + Box3D::Axis axis2 = Box3D::get_remaining_axes (front_rear_axis).second; + Box3D::Axis front_plane = Box3D::orth_plane_or_axis (front_rear_axis); + + std::vector on_hull; + std::vector inside_hull; + std::vector visible_faces; + + sp_3dbox_corner_configuration (box, on_hull, inside_hull); + + switch (on_hull.size()) { + case 4: + { + // the following works because on_hull is sorted + gint front_face = sp_3dbox_face_containing_diagonal_corners (on_hull[0], on_hull[3]); + visible_faces.push_back (front_face); + } + break; + + case 6: + { + guint c1 = inside_hull[0] ^ Box3D::XYZ; + guint c2 = inside_hull[1] ^ Box3D::XYZ; + Box3D::Axis edge = (Box3D::Axis) (c1 ^ c2); + if (Box3D::is_single_axis_direction (edge)) { + visible_faces = sp_3dbox_adjacent_faces_of_edge (c1, c2); + } else if (c1 == c2 ^ Box3D::XYZ) { + guint c_cmp = sp_3dbox_get_corner_id_along_edge (box, 0, front_rear_axis, Box3D::FRONT); + guint visible_front_corner = (((c_cmp & front_rear_axis) == (c1 & front_rear_axis)) ? c1 : c2); + visible_faces = sp_3dbox_faces_meeting_in_corner (visible_front_corner); + } else { + g_print ("Warning: Unhandled case. Current z-orders remain unchanged.\n"); + return false; + } + break; + } + + default: + g_print ("Warning: Unhandled case. Current z-orders are not changed.\n"); + return false; + } + + // check for weird corner configurations that cannot be handled by the above code + if (std::find (visible_faces.begin(), visible_faces.end(), -1) != visible_faces.end()) { + g_warning ("Theoretically impossible corner configuration\n"); + return false; + } + + // sort the list of visible faces for later use (although it may be already sorted anyway) + std::sort (visible_faces.begin(), visible_faces.end()); + + std::vector invisible_faces; + sp_3dbox_remaining_faces (visible_faces, invisible_faces); + + + if (!sp_3dbox_is_subset_or_superset (visible_faces, box->currently_visible_faces) && + !sp_3dbox_differ_by_opposite_faces (visible_faces, box->currently_visible_faces)) { + std::swap (visible_faces, invisible_faces); + if (!sp_3dbox_is_subset_or_superset (visible_faces, box->currently_visible_faces) && + !sp_3dbox_differ_by_opposite_faces (visible_faces, box->currently_visible_faces)) { + // FIXME: Hopefully this case is only caused by rounding errors or something similar; + // does it need further investigation? + g_warning ("Can't find out which faces are visible and which aren't ...\n"); + return false; + } + } + + box->currently_visible_faces = visible_faces; + + // set new z-orders according to the visible/invisible faces + guint vis_size = visible_faces.size(); + for (guint i = 0; i < vis_size; ++i) { + new_z_orders[i] = visible_faces[i]; + } + for (guint i = 0; i < invisible_faces.size(); ++i) { + new_z_orders[vis_size + i] = invisible_faces[i]; + } + + // test whether any z-orders actually changed and indicate this in the return status + for (int i = 0; i < 6; ++i) { + if (box->z_orders[i] != new_z_orders[i]) { + // we update the z-orders starting from the index where the change occurs + for (int j = i; j < 6; ++j) { + box->z_orders[j] = new_z_orders[j]; + } + return true; + } + } + return false; +} + +// FIXME: Can we unify this and the next function for setting the z-orders? +void sp_3dbox_set_z_orders_in_the_first_place (SP3DBox *box) { // For efficiency reasons, we only set the new z-orders if something really changed if (sp_3dbox_recompute_z_orders (box)) { @@ -510,6 +744,19 @@ void sp_3dbox_set_z_orders (SP3DBox *box) } } +void sp_3dbox_set_z_orders_later_on (SP3DBox *box) +{ + // For efficiency reasons, we only set the new z-orders if something really changed + if (sp_3dbox_recompute_z_orders_by_corner_configuration (box)) { + box->faces[box->z_orders[0]]->lower_to_bottom (); + box->faces[box->z_orders[1]]->lower_to_bottom (); + box->faces[box->z_orders[2]]->lower_to_bottom (); + box->faces[box->z_orders[3]]->lower_to_bottom (); + box->faces[box->z_orders[4]]->lower_to_bottom (); + box->faces[box->z_orders[5]]->lower_to_bottom (); + } +} + void sp_3dbox_update_curves (SP3DBox *box) { for (int i = 0; i < 6; ++i) { diff --git a/src/box3d.h b/src/box3d.h index e1b90c3f9..57c4f0e9b 100644 --- a/src/box3d.h +++ b/src/box3d.h @@ -38,6 +38,8 @@ struct SP3DBox : public SPGroup { Box3DFace *faces[6]; guint z_orders[6]; // z_orders[i] holds the ID of the face at position #i in the group (from top to bottom) + std::vector currently_visible_faces; + // TODO: Keeping/updating the ratios works reasonably well but is still an ad hoc implementation. // Use a mathematically correct model to update the boxes. double ratio_x; @@ -68,9 +70,8 @@ GType sp_3dbox_get_type (void); void sp_3dbox_position_set (SP3DBoxContext &bc); void sp_3dbox_set_shape(SP3DBox *box3d, bool use_previous_corners = false); void sp_3dbox_recompute_corners (SP3DBox *box, NR::Point const pt1, NR::Point const pt2, NR::Point const pt3); -bool sp_3dbox_recompute_z_orders (SP3DBox *box); /* returns true if there was a change in the z-orders - (which triggers an update of the repr) */ -void sp_3dbox_set_z_orders (SP3DBox *box); +void sp_3dbox_set_z_orders_in_the_first_place (SP3DBox *box); +void sp_3dbox_set_z_orders_later_on (SP3DBox *box); void sp_3dbox_update_curves (SP3DBox *box); void sp_3dbox_link_to_existing_paths (SP3DBox *box, Inkscape::XML::Node *repr); void sp_3dbox_set_ratios (SP3DBox *box, Box3D::Axis axes = Box3D::XYZ); diff --git a/src/line-geometry.cpp b/src/line-geometry.cpp index f6f411bff..000da8a07 100644 --- a/src/line-geometry.cpp +++ b/src/line-geometry.cpp @@ -100,8 +100,8 @@ std::pair coordinates (NR::Point const &v1, NR::Point const &v2, { double det = determinant (v1, v2);; if (fabs (det) < epsilon) { - g_warning ("Vectors do not form a basis.\n"); - return std::make_pair (0.0, 0.0); + // vectors are not linearly independent; we indicate this in the return value(s) + return std::make_pair (HUGE_VAL, HUGE_VAL); } double lambda1 = determinant (w, v2) / det; @@ -113,6 +113,11 @@ std::pair coordinates (NR::Point const &v1, NR::Point const &v2, bool lies_in_sector (NR::Point const &v1, NR::Point const &v2, NR::Point const &w) { std::pair coords = coordinates (v1, v2, w); + if (coords.first == HUGE_VAL) { + // catch the case that the vectors are not linearly independent + // FIXME: Can we assume that it's safe to return true if the vectors point in different directions? + return (NR::dot (v1, v2) < 0); + } return (coords.first >= 0 and coords.second >= 0); } diff --git a/src/object-edit.cpp b/src/object-edit.cpp index bb98c6b68..40e38a393 100644 --- a/src/object-edit.cpp +++ b/src/object-edit.cpp @@ -646,19 +646,22 @@ static void sp_3dbox_knot_set(SPItem *item, guint knot_id, NR::Point const &new_ sp_3dbox_update_curves (box); sp_3dbox_set_ratios (box); sp_3dbox_update_perspective_lines (); - sp_3dbox_set_z_orders (box); + sp_3dbox_set_z_orders_later_on (box); } static void sp_3dbox_knot_center_set(SPItem *item, NR::Point const &new_pos, NR::Point const &origin, guint state) { + SP3DBox *box = SP_3DBOX(item); + NR::Matrix const i2d (sp_item_i2d_affine (item)); if (state & GDK_SHIFT_MASK) { - sp_3dbox_recompute_Z_corners_from_new_center (SP_3DBOX (item), new_pos * i2d); + sp_3dbox_recompute_Z_corners_from_new_center (box, new_pos * i2d); } else { - sp_3dbox_recompute_XY_corners_from_new_center (SP_3DBOX (item), new_pos * i2d); + sp_3dbox_recompute_XY_corners_from_new_center (box, new_pos * i2d); } - sp_3dbox_update_curves (SP_3DBOX(item)); + sp_3dbox_update_curves (box); + sp_3dbox_set_z_orders_later_on (box); } static NR::Point sp_3dbox_knot_center_get(SPItem *item) diff --git a/src/perspective3d.cpp b/src/perspective3d.cpp index e2b9fcbc2..9f79d25bd 100644 --- a/src/perspective3d.cpp +++ b/src/perspective3d.cpp @@ -327,7 +327,7 @@ void Perspective3D::update_z_orders () { for (GSList *i = this->boxes; i != NULL; i = i->next) { - sp_3dbox_set_z_orders (SP_3DBOX (i->data)); + sp_3dbox_set_z_orders_later_on (SP_3DBOX (i->data)); } } -- 2.30.2