space_view3d_enhanced_3d_cursor.py

        self.transform_orientation = name

        if set_v3d:
            self.v3d.transform_orientation = name

    def get_matrix(self, name=None):
        active_obj = self.view_layer.objects.active

        if not name:
            name = self.transform_orientation

        if self.is_custom:
            matrix = self.custom_systems[self.custom_id].matrix.copy()
        else:
            if (name == 'VIEW') and self.rv3d:
                matrix = self.rv3d.view_rotation.to_matrix()
            elif name == "Surface":
                matrix = self.get_custom(name).matrix.copy()
            elif (name == 'GLOBAL') or (not active_obj):
                matrix = Matrix().to_3x3()
            elif (name == 'NORMAL') and self.normal_system:
                matrix = self.normal_system.copy()
            else:
                matrix = active_obj.matrix_world.to_3x3()
                if name == "Scaled":
                    self.get_custom(name).matrix = matrix
                else: # 'LOCAL', 'GIMBAL', ['NORMAL'] for now
                    matrix[0].normalize()
                    matrix[1].normalize()
                    matrix[2].normalize()

        return matrix

    def get_custom(self, name):
        try:
            return self.scene.orientations[name]
        except:
            return create_transform_orientation(
                self.scene, name, Matrix())

# Is there a less cumbersome way to create transform orientation?
def create_transform_orientation(scene, name=None, matrix=None):
    active_obj = view_layer.objects.active
    prev_mode = None

    if active_obj:
        prev_mode = active_obj.mode
        bpy.ops.object.mode_set(mode='OBJECT')
    else:
        bpy.ops.object.add()

    # ATTENTION! This uses context's scene
    bpy.ops.transform.create_orientation()

    tfm_orient = scene.orientations[-1]

    if name is not None:
        basename = name
        i = 1
        while name in scene.orientations:
            name = "%s.%03i" % (basename, i)
            i += 1
        tfm_orient.name = name

    if matrix:
        tfm_orient.matrix = matrix.to_3x3()

    if active_obj:
        bpy.ops.object.mode_set(mode=prev_mode)
    else:
        bpy.ops.object.delete()

    return tfm_orient

# ====== VIEW UTILITY CLASS ====== #
class ViewUtility:
    methods = dict(
        get_locks = lambda: {},
        set_locks = lambda locks: None,
        get_position = lambda: Vector(),
        set_position = lambda: None,
        get_rotation = lambda: Quaternion(),
        get_direction = lambda: Vector((0, 0, 1)),
        get_viewpoint = lambda: Vector(),
        get_matrix = lambda: Matrix(),
        get_point = lambda xy, pos: \
            Vector((xy[0], xy[1], 0)),
        get_ray = lambda xy: tuple(
            Vector((xy[0], xy[1], 0)),
            Vector((xy[0], xy[1], 1)),
            False),
    )

    def __init__(self, region, space_data, region_data):
        self.region = region
        self.space_data = space_data
        self.region_data = region_data

        if space_data.type == 'VIEW_3D':
            self.implementation = View3DUtility(
                region, space_data, region_data)
        else:
            self.implementation = None

        if self.implementation:
            for name in self.methods:
                setattr(self, name,
                    getattr(self.implementation, name))
        else:
            for name, value in self.methods.items():
                setattr(self, name, value)

class View3DUtility:
    lock_types = {"lock_cursor": False, "lock_object": None, "lock_bone": ""}

    # ====== INITIALIZATION / CLEANUP ====== #
    def __init__(self, region, space_data, region_data):
        self.region = region
        self.space_data = space_data
        self.region_data = region_data

    # ====== GET VIEW MATRIX AND ITS COMPONENTS ====== #
    def get_locks(self):
        v3d = self.space_data
        return {k:getattr(v3d, k) for k in self.lock_types}

    def set_locks(self, locks):
        v3d = self.space_data
        for k in self.lock_types:
            setattr(v3d, k, locks.get(k, self.lock_types[k]))

    def _get_lock_obj_bone(self):
        v3d = self.space_data

        obj = v3d.lock_object
        if not obj:
            return None, None

        if v3d.lock_bone:
            try:
                # this is not tested!
                if obj.mode == 'EDIT':
                    bone = obj.data.edit_bones[v3d.lock_bone]
                else:
                    bone = obj.data.bones[v3d.lock_bone]
            except:
                bone = None
        else:
            bone = None

        return obj, bone

    # TODO: learn how to get these values from
    # rv3d.perspective_matrix and rv3d.view_matrix ?
    def get_position(self, no_locks=False):
        v3d = self.space_data
        rv3d = self.region_data

        if no_locks:
            return rv3d.view_location.copy()

        # rv3d.perspective_matrix and rv3d.view_matrix
        # seem to have some weird translation components %)

        if rv3d.view_perspective == 'CAMERA':
            p = v3d.camera.matrix_world.to_translation()
            d = self.get_direction()
            return p + d * rv3d.view_distance
        else:
            if v3d.lock_object:
                obj, bone = self._get_lock_obj_bone()
                if bone:
                    return (obj.matrix_world * bone.matrix).to_translation()
                else:
                    return obj.matrix_world.to_translation()
            elif v3d.lock_cursor:
                return get_cursor_location(v3d=v3d)
            else:
                return rv3d.view_location.copy()

    def set_position(self, pos, no_locks=False):
        v3d = self.space_data
        rv3d = self.region_data

        pos = pos.copy()

        if no_locks:
            rv3d.view_location = pos
            return

        if rv3d.view_perspective == 'CAMERA':
            d = self.get_direction()
            v3d.camera.matrix_world.translation = pos - d * rv3d.view_distance
        else:
            if v3d.lock_object:
                obj, bone = self._get_lock_obj_bone()
                if bone:
                    try:
                        bone.matrix.translation = \
                            obj.matrix_world.inverted() * pos
                    except:
                        # this is some degenerate object
                        bone.matrix.translation = pos
                else:
                    obj.matrix_world.translation = pos
            elif v3d.lock_cursor:
                set_cursor_location(pos, v3d=v3d)
            else:
                rv3d.view_location = pos

    def get_rotation(self):
        v3d = self.space_data
        rv3d = self.region_data

        if rv3d.view_perspective == 'CAMERA':
            return v3d.camera.matrix_world.to_quaternion()
        else:
            return rv3d.view_rotation

    def get_direction(self):
        # Camera (as well as viewport) looks in the direction of -Z;
        # Y is up, X is left
        d = self.get_rotation() * Vector((0, 0, -1))
        d.normalize()
        return d

    def get_viewpoint(self):
        v3d = self.space_data
        rv3d = self.region_data

        if rv3d.view_perspective == 'CAMERA':
            return v3d.camera.matrix_world.to_translation()
        else:
            p = self.get_position()
            d = self.get_direction()
            return p - d * rv3d.view_distance

    def get_matrix(self):
        m = self.get_rotation().to_matrix()
        m.resize_4x4()
        m.translation = self.get_viewpoint()
        return m

    def get_point(self, xy, pos):
        region = self.region
        rv3d = self.region_data
        return region_2d_to_location_3d(region, rv3d, xy, pos)

    def get_ray(self, xy):
        region = self.region
        v3d = self.space_data
        rv3d = self.region_data

        viewPos = self.get_viewpoint()
        viewDir = self.get_direction()

        near = viewPos + viewDir * v3d.clip_start
        far = viewPos + viewDir * v3d.clip_end

        a = region_2d_to_location_3d(region, rv3d, xy, near)
        b = region_2d_to_location_3d(region, rv3d, xy, far)

        # When viewed from in-scene camera, near and far
        # planes clip geometry even in orthographic mode.
        clip = rv3d.is_perspective or (rv3d.view_perspective == 'CAMERA')

        return a, b, clip

# ====== SNAP UTILITY CLASS ====== #
class SnapUtility:
    def __init__(self, context):
        if context.area.type == 'VIEW_3D':
            v3d = context.space_data
            shade = v3d.viewport_shade
            self.implementation = Snap3DUtility(context, shade)
            self.implementation.update_targets(
                context.visible_objects, [])

    def dispose(self):
        self.implementation.dispose()

    def update_targets(self, to_include, to_exclude):
        self.implementation.update_targets(to_include, to_exclude)

    def set_modes(self, **kwargs):
        return self.implementation.set_modes(**kwargs)

    def snap(self, *args, **kwargs):
        return self.implementation.snap(*args, **kwargs)

class SnapUtilityBase:
    def __init__(self):
        self.targets = set()
        # TODO: set to current blend settings?
        self.interpolation = 'NEVER'
        self.editmode = False
        self.snap_type = None
        self.projection = [None, None, None]
        self.potential_snap_elements = None
        self.extra_snap_points = None

    def update_targets(self, to_include, to_exclude):
        self.targets.update(to_include)
        self.targets.difference_update(to_exclude)

    def set_modes(self, **kwargs):
        if "use_relative_coords" in kwargs:
            self.use_relative_coords = kwargs["use_relative_coords"]
        if "interpolation" in kwargs:
            # NEVER, ALWAYS, SMOOTH
            self.interpolation = kwargs["interpolation"]
        if "editmode" in kwargs:
            self.editmode = kwargs["editmode"]
        if "snap_align" in kwargs:
            self.snap_align = kwargs["snap_align"]
        if "snap_type" in kwargs:
            # 'INCREMENT', 'VERTEX', 'EDGE', 'FACE', 'VOLUME'
            self.snap_type = kwargs["snap_type"]
        if "axes_coords" in kwargs:
            # none, point, line, plane
            self.axes_coords = kwargs["axes_coords"]

    # ====== CURSOR REPOSITIONING ====== #
    def snap(self, xy, src_matrix, initial_matrix, do_raycast, \
        alt_snap, vu, csu, modify_Surface, use_object_centers):

        v3d = csu.space_data

        grid_step = self.grid_steps[alt_snap] * v3d.grid_scale

        su = self
        use_relative_coords = su.use_relative_coords
        snap_align = su.snap_align
        axes_coords = su.axes_coords
        snap_type = su.snap_type

        runtime_settings = find_runtime_settings()

        matrix = src_matrix.to_3x3()
        pos = src_matrix.to_translation().copy()

        sys_matrix = csu.get_matrix()
        if use_relative_coords:
            sys_matrix.translation = initial_matrix.translation.copy()

        # Axes of freedom and line/plane parameters
        start = Vector(((0 if v is None else v) for v in axes_coords))
        direction = Vector(((v is not None) for v in axes_coords))
        axes_of_freedom = 3 - int(sum(direction))

        # do_raycast is False when mouse is not moving
        if do_raycast:
            su.hide_bbox(True)

            self.potential_snap_elements = None
            self.extra_snap_points = None

            set_stick_obj(csu.tou.scene, None)

            raycast = None
            snap_to_obj = (snap_type != 'INCREMENT') #or use_object_centers
            snap_to_obj = snap_to_obj and (snap_type is not None)
            if snap_to_obj:
                a, b, clip = vu.get_ray(xy)
                view_dir = vu.get_direction()
                raycast = su.snap_raycast(a, b, clip, view_dir, csu, alt_snap)

            if raycast:
                surf_matrix, face_id, obj, orig_obj = raycast

                if not use_object_centers:
                    self.potential_snap_elements = [
                        (obj.matrix_world * obj.data.vertices[vi].co)
                        for vi in obj.data.polygons[face_id].vertices
                    ]

                if use_object_centers:
                    self.extra_snap_points = \
                        [obj.matrix_world.to_translation()]
                elif alt_snap:
                    pse = self.potential_snap_elements
                    n = len(pse)
                    if self.snap_type == 'EDGE':
                        self.extra_snap_points = []
                        for i in range(n):
                            v0 = pse[i]
                            v1 = pse[(i + 1) % n]
                            self.extra_snap_points.append((v0 + v1) / 2)
                    elif self.snap_type == 'FACE':
                        self.extra_snap_points = []
                        v0 = Vector()
                        for v1 in pse:
                            v0 += v1
                        self.extra_snap_points.append(v0 / n)

                if snap_align:
                    matrix = surf_matrix.to_3x3()

                if not use_object_centers:
                    pos = surf_matrix.to_translation()
                else:
                    pos = orig_obj.matrix_world.to_translation()

                try:
                    local_pos = orig_obj.matrix_world.inverted() * pos
                except:
                    # this is some degenerate object
                    local_pos = pos

                set_stick_obj(csu.tou.scene, orig_obj.name, local_pos)

                modify_Surface = modify_Surface and \
                    (snap_type != 'VOLUME') and (not use_object_centers)

                # === Update "Surface" orientation === #
                if modify_Surface:
                    # Use raycast[0], not matrix! If snap_align == False,
                    # matrix will be src_matrix!
                    coordsys = csu.tou.get_custom("Surface")
                    coordsys.matrix = surf_matrix.to_3x3()
                    runtime_settings.surface_pos = pos
                    if csu.tou.get() == "Surface":
                        sys_matrix = to_matrix4x4(matrix, pos)
            else:
                if axes_of_freedom == 0:
                    # Constrained in all axes, can't move.
                    pass
                elif axes_of_freedom == 3:
                    # Not constrained, move in view plane.
                    pos = vu.get_point(xy, pos)
                else:
                    a, b, clip = vu.get_ray(xy)
                    view_dir = vu.get_direction()

                    start = sys_matrix * start

                    if axes_of_freedom == 1:
                        direction = Vector((1, 1, 1)) - direction
                    direction.rotate(sys_matrix)

                    if axes_of_freedom == 2:
                        # Constrained in one axis.
                        # Find intersection with plane.
                        i_p = intersect_line_plane(a, b, start, direction)
                        if i_p is not None:
                            pos = i_p
                    elif axes_of_freedom == 1:
                        # Constrained in two axes.
                        # Find nearest point to line.
                        i_p = intersect_line_line(a, b, start,
                                                  start + direction)
                        if i_p is not None:
                            pos = i_p[1]
        #end if do_raycast

        try:
            sys_matrix_inv = sys_matrix.inverted()
        except:
            # this is some degenerate system
            sys_matrix_inv = Matrix()

        _pos = sys_matrix_inv * pos

        # don't snap when mouse hasn't moved
        if (snap_type == 'INCREMENT') and do_raycast:
            for i in range(3):
                _pos[i] = round_step(_pos[i], grid_step)

        for i in range(3):
            if axes_coords[i] is not None:
                _pos[i] = axes_coords[i]

        if (snap_type == 'INCREMENT') or (axes_of_freedom != 3):
            pos = sys_matrix * _pos

        res_matrix = to_matrix4x4(matrix, pos)

        CursorDynamicSettings.local_matrix = \
            sys_matrix_inv * res_matrix

        return res_matrix

class Snap3DUtility(SnapUtilityBase):
    grid_steps = {False:1.0, True:0.1}

    cube_verts = [Vector((i, j, k))
        for i in (-1, 1)
        for j in (-1, 1)
        for k in (-1, 1)]

    def __init__(self, context, shade):
        SnapUtilityBase.__init__(self)

        convert_types = {'MESH', 'CURVE', 'SURFACE', 'FONT', 'META'}
        self.cache = MeshCache(context, convert_types)

        # ? seems that dict is enough
        self.bbox_cache = {}#collections.OrderedDict()
        self.sys_matrix_key = [0.0] * 9

        bm = prepare_gridbox_mesh(subdiv=2)
        mesh = bpy.data.meshes.new(tmp_name)
        bm.to_mesh(mesh)
        mesh.update(calc_tessface=True)
        #mesh.calc_tessface()

        self.bbox_obj = self.cache._make_obj(mesh, None)
        self.bbox_obj.hide = True
        self.bbox_obj.display_type = 'WIRE'
        self.bbox_obj.name = "BoundBoxSnap"

        self.shade_bbox = (shade == 'BOUNDBOX')

    def update_targets(self, to_include, to_exclude):
        settings = find_settings()
        tfm_opts = settings.transform_options
        only_solid = tfm_opts.snap_only_to_solid

        # Ensure this is a set and not some other
        # type of collection
        to_exclude = set(to_exclude)

        for target in to_include:
            if only_solid and ((target.display_type == 'BOUNDS') \
                    or (target.display_type == 'WIRE')):
                to_exclude.add(target)

        SnapUtilityBase.update_targets(self, to_include, to_exclude)

    def dispose(self):
        self.hide_bbox(True)

        mesh = self.bbox_obj.data
        bpy.data.objects.remove(self.bbox_obj)
        bpy.data.meshes.remove(mesh)

        self.cache.clear()

    def hide_bbox(self, hide):
        if self.bbox_obj.hide == hide:
            return

        self.bbox_obj.hide = hide

        # We need to unlink bbox until required to show it,
        # because otherwise outliner will blink each
        # time cursor is clicked
        if hide:
            self.cache.collection.objects.unlink(self.bbox_obj)
        else:
            self.cache.collection.objects.link(self.bbox_obj)

    def get_bbox_obj(self, obj, sys_matrix, sys_matrix_inv, is_local):
        if is_local:
            bbox = None
        else:
            bbox = self.bbox_cache.get(obj, None)

        if bbox is None:
            m = obj.matrix_world
            if is_local:
                sys_matrix = m.copy()
                try:
                    sys_matrix_inv = sys_matrix.inverted()
                except Exception:
                    # this is some degenerate system
                    sys_matrix_inv = Matrix()
            m_combined = sys_matrix_inv * m
            bbox = [None, None]

            variant = ('RAW' if (self.editmode and
                       (obj.type == 'MESH') and (obj.mode == 'EDIT'))
                       else 'PREVIEW')
            mesh_obj = self.cache.get(obj, variant, reuse=False)
            if (mesh_obj is None) or self.shade_bbox or \
                    (obj.display_type == 'BOUNDS'):
                if is_local:
                    bbox = [(-1, -1, -1), (1, 1, 1)]
                else:
                    for p in self.cube_verts:
                        extend_bbox(bbox, m_combined * p.copy())
            elif is_local:
                bbox = [mesh_obj.bound_box[0], mesh_obj.bound_box[6]]
            else:
                for v in mesh_obj.data.vertices:
                    extend_bbox(bbox, m_combined * v.co.copy())

            bbox = (Vector(bbox[0]), Vector(bbox[1]))

            if not is_local:
                self.bbox_cache[obj] = bbox

        half = (bbox[1] - bbox[0]) * 0.5

        m = MatrixCompose(half[0], half[1], half[2])
        m = sys_matrix.to_3x3() * m
        m.resize_4x4()
        m.translation = sys_matrix * (bbox[0] + half)
        self.bbox_obj.matrix_world = m

        return self.bbox_obj

    # TODO: ?
    # - Sort snap targets according to raycasted distance?
    # - Ignore targets if their bounding sphere is further
    #   than already picked position?
    # Perhaps these "optimizations" aren't worth the overhead.

    def raycast(self, a, b, clip, view_dir, is_bbox, \
                sys_matrix, sys_matrix_inv, is_local, x_ray):
        # If we need to interpolate normals or snap to
        # vertices/edges, we must convert mesh.
        #force = (self.interpolation != 'NEVER') or \
        #    (self.snap_type in {'VERTEX', 'EDGE'})
        # Actually, we have to always convert, since
        # we need to get face at least to find tangential.
        force = True
        edit = self.editmode

        res = None
        L = None

        for obj in self.targets:
            orig_obj = obj

            if obj.name == self.bbox_obj.name:
                # is there a better check?
                # ("a is b" doesn't work here)
                continue
            if obj.show_in_front != x_ray:
                continue

            if is_bbox:
                obj = self.get_bbox_obj(obj, \
                    sys_matrix, sys_matrix_inv, is_local)
            elif obj.display_type == 'BOUNDS':
                # Outside of BBox, there is no meaningful visual snapping
                # for such display mode
                continue

            m = obj.matrix_world.copy()
            try:
                mi = m.inverted()
            except:
                # this is some degenerate object
                continue
            la = mi * a
            lb = mi * b

            # Bounding sphere check (to avoid unnecesary conversions
            # and to make ray 'infinite')
            bb_min = Vector(obj.bound_box[0])
            bb_max = Vector(obj.bound_box[6])
            c = (bb_min + bb_max) * 0.5
            r = (bb_max - bb_min).length * 0.5
            sec = intersect_line_sphere(la, lb, c, r, False)
            if sec[0] is None:
                continue # no intersection with the bounding sphere

            if not is_bbox:
                # Ensure we work with raycastable object.
                variant = ('RAW' if (edit and
                           (obj.type == 'MESH') and (obj.mode == 'EDIT'))
                           else 'PREVIEW')
                obj = self.cache.get(obj, variant, reuse=(not force))
                if (obj is None) or (not obj.data.polygons):
                    continue # the object has no raycastable geometry

            # If ray must be infinite, ensure that
            # endpoints are outside of bounding volume
            if not clip:
                # Seems that intersect_line_sphere()
                # returns points in flipped order
                lb, la = sec

            def ray_cast(obj, la, lb):
                if bpy.app.version < (2, 77, 0):
                    # Object.ray_cast(start, end)
                    # returns (location, normal, index)
                    res = obj.ray_cast(la, lb)
                    return ((res[-1] >= 0), res[0], res[1], res[2])
                else:
                    # Object.ray_cast(origin, direction, [distance])
                    # returns (result, location, normal, index)
                    ld = lb - la
                    return obj.ray_cast(la, ld, ld.magnitude)

            # Does ray actually intersect something?
            try:
                success, lp, ln, face_id = ray_cast(obj, la, lb)
            except Exception as e:
                # Somewhy this seems to happen when snapping cursor
                # in Local View mode at least since r55223:
                # <<Object "\U0010ffff" has no mesh data to be used
                # for raycasting>> despite obj.data.polygons
                # being non-empty.
                try:
                    # Work-around: in Local View at least the object
                    # in focus permits raycasting (modifiers are
                    # applied in 'PREVIEW' mode)
                    success, lp, ln, face_id = ray_cast(orig_obj, la, lb)
                except Exception as e:
                    # However, in Edit mode in Local View we have
                    # no luck -- during the edit mode, mesh is
                    # inaccessible (thus no mesh data for raycasting).
                    #print(repr(e))
                    success = False

            if not success:
                continue

            # transform position to global space
            p = m * lp

            # This works both for prespective and ortho
            l = p.dot(view_dir)
            if (L is None) or (l < L):
                res = (lp, ln, face_id, obj, p, m, la, lb, orig_obj)
                L = l
        #end for

        return res

    # Returns:
    # Matrix(X -- tangential,
    #        Y -- 2nd tangential,
    #        Z -- normal,
    #        T -- raycasted/snapped position)
    # Face ID (-1 if not applicable)
    # Object (None if not applicable)
    def snap_raycast(self, a, b, clip, view_dir, csu, alt_snap):
        settings = find_settings()
        tfm_opts = settings.transform_options

        if self.shade_bbox and tfm_opts.snap_only_to_solid:
            return None

        # Since introduction of "use object centers",
        # this check is useless (use_object_centers overrides
        # even INCREMENT snapping)
        #if self.snap_type not in {'VERTEX', 'EDGE', 'FACE', 'VOLUME'}:
        #    return None

        # key shouldn't depend on system origin;
        # for bbox calculation origin is always zero
        #if csu.tou.get() != "Surface":
        #    sys_matrix = csu.get_matrix().to_3x3()
        #else:
        #    sys_matrix = csu.get_matrix('LOCAL').to_3x3()
        sys_matrix = csu.get_matrix().to_3x3()
        sys_matrix_key = list(c for v in sys_matrix for c in v)
        sys_matrix_key.append(self.editmode)
        sys_matrix = sys_matrix.to_4x4()
        try:
            sys_matrix_inv = sys_matrix.inverted()
        except:
            # this is some degenerate system
            return None

        if self.sys_matrix_key != sys_matrix_key:
            self.bbox_cache.clear()
            self.sys_matrix_key = sys_matrix_key

        # In this context, Volume represents BBox :P
        is_bbox = (self.snap_type == 'VOLUME')
        is_local = (csu.tou.get() in {'LOCAL', "Scaled"})

        res = self.raycast(a, b, clip, view_dir, \
            is_bbox, sys_matrix, sys_matrix_inv, is_local, True)

        if res is None:
            res = self.raycast(a, b, clip, view_dir, \
                is_bbox, sys_matrix, sys_matrix_inv, is_local, False)

        # Occlusion-based edge/vertex snapping will be
        # too inefficient in Python (well, even without
        # the occlusion, iterating over all edges/vertices
        # of each object is inefficient too)

        if not res:
            return None

        lp, ln, face_id, obj, p, m, la, lb, orig_obj = res

        if is_bbox:
            self.bbox_obj.matrix_world = m.copy()
            self.bbox_obj.show_in_front = orig_obj.show_in_front
            self.hide_bbox(False)

        _ln = ln.copy()

        face = obj.data.polygons[face_id]
        L = None
        t1 = None

        if self.snap_type == 'VERTEX' or self.snap_type == 'VOLUME':
            for v0 in face.vertices:
                v = obj.data.vertices[v0]
                p0 = v.co
                l = (lp - p0).length_squared
                if (L is None) or (l < L):
                    p = p0
                    ln = v.normal.copy()
                    #t1 = ln.cross(_ln)
                    L = l

            _ln = ln.copy()
            '''
            if t1.length < epsilon:
                if (1.0 - abs(ln.z)) < epsilon:
                    t1 = Vector((1, 0, 0))
                else:
                    t1 = Vector((0, 0, 1)).cross(_ln)
            '''
            p = m * p
        elif self.snap_type == 'EDGE':
            use_smooth = face.use_smooth
            if self.interpolation == 'NEVER':
                use_smooth = False
            elif self.interpolation == 'ALWAYS':
                use_smooth = True

            for v0, v1 in face.edge_keys:
                p0 = obj.data.vertices[v0].co
                p1 = obj.data.vertices[v1].co
                dp = p1 - p0
                q = dp.dot(lp - p0) / dp.length_squared
                if (q >= 0.0) and (q <= 1.0):
                    ep = p0 + dp * q
                    l = (lp - ep).length_squared
                    if (L is None) or (l < L):
                        if alt_snap:
                            p = (p0 + p1) * 0.5
                            q = 0.5
                        else:
                            p = ep
                        if not use_smooth:
                            q = 0.5
                        ln = obj.data.vertices[v1].normal * q + \
                             obj.data.vertices[v0].normal * (1.0 - q)
                        t1 = dp
                        L = l

            p = m * p
        else:
            if alt_snap:
                lp = face.center
                p = m * lp

            if self.interpolation != 'NEVER':
                ln = self.interpolate_normal(
                    obj, face_id, lp, la, lb - la)

            # Comment this to make 1st tangential
            # always lie in the face's plane
            _ln = ln.copy()

            '''
            for v0, v1 in face.edge_keys:
                p0 = obj.data.vertices[v0].co
                p1 = obj.data.vertices[v1].co
                dp = p1 - p0
                q = dp.dot(lp - p0) / dp.length_squared
                if (q >= 0.0) and (q <= 1.0):
                    ep = p0 + dp * q
                    l = (lp - ep).length_squared
                    if (L is None) or (l < L):
                        t1 = dp
                        L = l
            '''

        n = ln.copy()
        n.rotate(m)
        n.normalize()

        if t1 is None:
            _ln.rotate(m)
            _ln.normalize()
            if (1.0 - abs(_ln.z)) < epsilon:
                t1 = Vector((1, 0, 0))
            else:
                t1 = Vector((0, 0, 1)).cross(_ln)
            t1.normalize()
        else:
            t1.rotate(m)
            t1.normalize()

        t2 = t1.cross(n)
        t2.normalize()

        matrix = MatrixCompose(t1, t2, n, p)

        return (matrix, face_id, obj, orig_obj)

    def interpolate_normal(self, obj, face_id, p, orig, ray):
        face = obj.data.polygons[face_id]

        use_smooth = face.use_smooth
        if self.interpolation == 'NEVER':
            use_smooth = False
        elif self.interpolation == 'ALWAYS':
            use_smooth = True

        if not use_smooth:
            return face.normal.copy()

        # edge.use_edge_sharp affects smoothness only if
        # mesh has EdgeSplit modifier

        # ATTENTION! Coords/Normals MUST be copied
        # (a bug in barycentric_transform implementation ?)
        # Somewhat strangely, the problem also disappears
        # if values passed to barycentric_transform
        # are print()ed beforehand.

        co = [obj.data.vertices[vi].co.copy()
            for vi in face.vertices]

        normals = [obj.data.vertices[vi].normal.copy()
            for vi in face.vertices]

        if len(face.vertices) != 3:
            tris = tessellate_polygon([co])
            for tri in tris:
                i0, i1, i2 = tri
                if intersect_ray_tri(co[i0], co[i1], co[i2], ray, orig):
                    break
        else:
            i0, i1, i2 = 0, 1, 2

        n = barycentric_transform(p, co[i0], co[i1], co[i2],
            normals[i0], normals[i1], normals[i2])
        n.normalize()

        return n

# ====== CONVERTED-TO-MESH OBJECTS CACHE ====== #
#============================================================================#
class ToggleObjectMode:
    def __init__(self, mode='OBJECT'):
        if not isinstance(mode, str):
            mode = ('OBJECT' if mode else None)

        self.mode = mode

    def __enter__(self):
        if self.mode:
            edit_preferences = bpy.context.preferences.edit

            self.global_undo = edit_preferences.use_global_undo
            self.prev_mode = bpy.context.object.mode

            if self.prev_mode != self.mode:
                edit_preferences.use_global_undo = False
                bpy.ops.object.mode_set(mode=self.mode)

        return self

    def __exit__(self, type, value, traceback):
        if self.mode:
            edit_preferences = bpy.context.preferences.edit

            if self.prev_mode != self.mode:
                bpy.ops.object.mode_set(mode=self.prev_mode)
                edit_preferences.use_global_undo = self.global_undo

class MeshCacheItem:
    def __init__(self):
        self.variants = {}

    def __getitem__(self, variant):
        return self.variants[variant][0]

    def __setitem__(self, variant, conversion):
        mesh = conversion[0].data
        #mesh.update(calc_tessface=True)
        #mesh.calc_tessface()
        mesh.calc_normals()

        self.variants[variant] = conversion

    def __contains__(self, variant):
        return variant in self.variants

    def dispose(self):
        for obj, converted in self.variants.values():
            if converted:
                mesh = obj.data
                bpy.data.objects.remove(obj)
                bpy.data.meshes.remove(mesh)
        self.variants = None

class MeshCache:
    """
    Keeps a cache of mesh equivalents of requested objects.
    It is assumed that object's data does not change while
    the cache is in use.
    """