Region-selection of objects in Panda3D

main.py

from panda3d.core import *
from direct.showbase.ShowBase import ShowBase
from direct.showbase.DirectObject import DirectObject
from region_selection import RegionSelector


class MyApp(ShowBase):

    def __init__(self):

        ShowBase.__init__(self)

        self.use_secondary_display_region = False
        self.customize_key_bindings = False
        self.use_built_in_cam_controller = False

        if self.use_built_in_cam_controller and not self.use_secondary_display_region:
            self.trackball.node().set_pos(0., 50., 0.)
            self.customize_key_bindings = True
        else:
            self.disable_mouse()
            self.camera.set_pos(0., -50., 0.)

        if self.use_secondary_display_region:
            dr3d = self.win.make_display_region(.4, .9, .2, .8)
            dr3d.sort = 1
            dr3d.clear_color = (.2, .5, .2, 1.)
            dr3d.set_clear_color_active(True)
            dr3d.set_clear_depth_active(True)
            self.dr2d = dr2d = self.win.make_display_region(.4, .9, .2, .8)
            dr2d.sort = 2
            self.root3d = NodePath("root3d")
            cam = Camera("3d")
            self.cam3d = self.root3d.attach_new_node(cam)
            self.cam3d.set_pos(0., -50., 0.)
            dr3d.camera = self.cam3d
            root2d = NodePath("root2d")
            cam = Camera("2d")
            lens = OrthographicLens()
            lens.film_size = (2., 2.)
            lens.near = -10.
            cam.set_lens(lens)
            self.cam2d = root2d.attach_new_node(cam)
            dr2d.camera = self.cam2d
            self.node2d = root2d.attach_new_node("node2d")
            self.node2d.set_pos(-1., 0., 1.)
            w, h = dr2d.pixel_size
            self.node2d.set_scale(2. / w, 1., 2. / h)
            self.mouse_watcher = MouseWatcher("viewport")
            self.mouse_watcher.set_display_region(dr3d)
            self.mouseWatcher.parent.attach_new_node(self.mouse_watcher)
            self.selector = RegionSelector(self, dr2d, self.node2d, self.cam2d,
                self.cam3d, self.mouse_watcher)
            root_node = self.root3d
        else:
            self.selector = RegionSelector(self)
            root_node = self.render

        self.selection_color = (1., 0., 0., 1.)

        self.selector.deselect_func = self.deselect_objects
        self.selector.select_func = self.select_objects
        self.selector.shape_border_color = (.4, .4, 1., 1.)
        self.selector.shape_fill_color = (.5, 1., .5, .4)

        for i in range(11):
            for j in range(7):
                smiley = self.loader.load_model("smiley")
                smiley.reparent_to(root_node)
                smiley.set_pos(2.5 * i - 12.5, 0., 2.5 * j - 7.5)
                self.selector.add(smiley)

        # print the names of the events that keys can be bound to
        print("Events available for key re-binding:\n", self.selector.event_ids)

        if self.customize_key_bindings:
            # the "set_first_region_point" event starts drawing the region-shape
            self.selector.bind("set_first_region_point", ["v"])
            # the "set_next_region_point" event adds a point to a fence shape,
            # but finalizes region-selection if any other shape is used
            self.selector.bind("set_next_region_point", ["v-up"])
            # completely replace all key-bindings for canceling region-selection...
#            self.selector.bind("cancel_region_select", ["x", "escape"])
            # ...or selectively add new...
            self.selector.bind("cancel_region_select", ["x"], add=True)
            # ...and remove existing key-bindings
            self.selector.unbind("cancel_region_select", ["mouse3"])

        def set_region_shape(shape_type):
            self.selector.shape_type = shape_type

        self.listener = listener = DirectObject()
        listener.accept("r", lambda: set_region_shape("rect"))
        listener.accept("s", lambda: set_region_shape("square"))
        listener.accept("c", lambda: set_region_shape("circle"))
        listener.accept("e", lambda: set_region_shape("ellipse"))
        listener.accept("shift-r", lambda: set_region_shape("rect_centered"))
        listener.accept("shift-s", lambda: set_region_shape("square_centered"))
        listener.accept("shift-c", lambda: set_region_shape("circle_centered"))
        listener.accept("shift-e", lambda: set_region_shape("ellipse_centered"))
        listener.accept("l", lambda: set_region_shape("lasso"))
        listener.accept("f", lambda: set_region_shape("fence"))
        listener.accept("p", lambda: set_region_shape("paint"))

        def toggle_enclose():
            self.selector.enclose = not self.selector.enclose

            if self.selector.enclose:
                self.selector.shape_border_color = (1., 0., 0., 1.)
            else:
                self.selector.shape_border_color = (.4, .4, 1., 1.)

        listener.accept("control-e", toggle_enclose)

        if self.use_secondary_display_region:
            listener.accept("window-event", self.handle_window_resize)

    def deselect_objects(self, objs):

        # remove color tint from deselected objects
        for obj in objs:
            obj.clear_color_scale()

    def select_objects(self, objs):

        # set the tint of the selected objects to the selection color
        for obj in objs:
            obj.set_color_scale(self.selection_color)

    def handle_window_resize(self, window):

        # update the scale of the 2D root node according to the new
        # pixel-size of the secondary display region
        w, h = self.dr2d.pixel_size
        self.node2d.set_scale(2. / w, 1., 2. / h)

        # also update the aspect ratio of the 3D camera
        angle_h = 35.
        angle_v = angle_h * h / w
        self.cam3d.node().get_lens().fov = (angle_h, angle_v)


app = MyApp()
app.run()

region_selection.py

# MIT License

# Copyright (c) 2021 Epihaius

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

from panda3d.core import *
from direct.showbase.DirectObject import DirectObject
import math


# The following vertex shader is used to region-select objects
VERT_SHADER = """
    #version 420

    uniform mat4 p3d_ModelViewProjectionMatrix;
    in vec4 p3d_Vertex;
    uniform int region_sel_index;
    flat out int oindex;

    void main() {
        gl_Position = p3d_ModelViewProjectionMatrix * p3d_Vertex;
        oindex = region_sel_index;
    }
"""

# The following fragment shader is used to determine which objects lie within
# a rectangular region
FRAG_SHADER = """
    #version 420

    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {
        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));
    }
"""

# The following fragment shader is used to constrain the selection to an
# elliptic region
FRAG_SHADER_ELLIPSE = """
    #version 420

    uniform vec4 ellipse_data;
    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {

        float radius, aspect_ratio, offset_x, offset_y, x, y, dist;

        radius = ellipse_data.x;
        aspect_ratio = ellipse_data.y;
        // the ellipse might be clipped by the viewport border, so it is
        // necessary to know the left and bottom offsets of this clipped
        // portion
        offset_x = ellipse_data.z;
        offset_y = ellipse_data.w;
        ivec2 coord = ivec2(gl_FragCoord.xy);
        x = offset_x + coord.x - radius;
        y = (offset_y + coord.y) * aspect_ratio - radius;
        dist = sqrt((x * x) + (y * y));

        // only consider pixels that are inside of the ellipse
        if (dist > radius) {
            discard;
        }

        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));

    }
"""

# The following fragment shader is used to constrain the selection to a
# free-form (point-to-point "fence", lasso or painted) region
FRAG_SHADER_FREE = """
    #version 420

    uniform sampler2D mask_tex;
    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {

        vec4 texelValue = texelFetch(mask_tex, ivec2(gl_FragCoord.xy), 0);

        // discard pixels whose corresponding mask texels are (0., 0., 0., 0.)
        if (texelValue == vec4(0., 0., 0., 0.)) {
            discard;
        }

        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));

    }
"""


# The following fragment shader is used to determine which objects are
# not completely enclosed within a rectangular region
FRAG_SHADER_INV = """
    #version 420

    uniform vec2 buffer_size;
    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {

        int w, h, x, y;

        w = int(buffer_size.x);
        h = int(buffer_size.y);
        x = int(gl_FragCoord.x);
        y = int(gl_FragCoord.y);

        // only consider border pixels
        if ((x > 1) && (x < w) && (y > 1) && (y < h)) {
            discard;
        }

        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));

    }
"""

# The following fragment shader is used to determine which objects are
# not completely enclosed within an elliptic region
FRAG_SHADER_ELLIPSE_INV = """
    #version 420

    uniform vec4 ellipse_data;
    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {

        float radius, aspect_ratio, offset_x, offset_y, x, y, dist;

        radius = ellipse_data.x;
        aspect_ratio = ellipse_data.y;
        // the ellipse might be clipped by the viewport border, so it is
        // necessary to know the left and bottom offsets of this clipped
        // portion
        offset_x = ellipse_data.z;
        offset_y = ellipse_data.w;
        ivec2 coord = ivec2(gl_FragCoord.xy);
        x = offset_x + coord.x - 2 - radius;
        y = (offset_y + coord.y - 2) * aspect_ratio - radius;
        dist = sqrt((x * x) + (y * y));

        // only consider pixels that are outside of the ellipse
        if (dist <= radius) {
            discard;
        }

        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));

    }
"""

# The following fragment shader is used to determine which objects are not
# completely enclosed within a free-form (fence, lasso or painted) region
FRAG_SHADER_FREE_INV = """
    #version 420

    uniform sampler2D mask_tex;
    layout(r32i) uniform iimageBuffer selections;
    flat in int oindex;

    void main() {

        vec4 texelValue = texelFetch(mask_tex, ivec2(gl_FragCoord.xy), 0);

        // only consider pixels whose corresponding mask texels are (0., 0., 0., 0.)
        if (texelValue != vec4(0., 0., 0., 0.)) {
            discard;
        }

        // Write 1 to the location corresponding to the custom index
        imageAtomicOr(selections, (oindex >> 5), 1 << (oindex & 31));

    }
"""


# The following shaders are used to gradually create a mask texture that can
# in turn be used as input for the free-form region-selection fragment shaders.

VERT_SHADER_MASK = """
    #version 420

    uniform mat4 p3d_ModelViewProjectionMatrix;
    in vec4 p3d_Vertex;

    void main() {
        gl_Position = p3d_ModelViewProjectionMatrix * p3d_Vertex;
    }
"""

FRAG_SHADER_MASK = """
    #version 420

    uniform sampler2D prev_tex;
    uniform vec4 fill_color;
    layout(location = 0) out vec4 out_color;

    void main() {

        vec4 texelValue = texelFetch(prev_tex, ivec2(gl_FragCoord.xy), 0);

        if (texelValue == vec4(0., 0., 0., 0.)) {
            out_color = fill_color;
        }
        else {
            out_color = vec4(0., 0., 0., 0.);
        }

    }
"""


class RegionSelectables:

    used_indices = BitArray()
    obj_indices = {}
    objs = {}

    @classmethod
    def add(cls, obj):

        if obj in cls.objs.values():
            return

        index = cls.used_indices.get_lowest_off_bit()
        cls.used_indices.set_bit(index)
        cls.obj_indices[obj] = index
        cls.objs[index] = obj
        obj.set_shader_input("region_sel_index", index)

    @classmethod
    def remove(cls, obj):

        if obj not in cls.objs.values():
            return

        index = cls.obj_indices[obj]
        del cls.obj_indices[obj]
        del cls.objs[index]
        cls.used_indices.clear_bit(index)
        obj.clear_shader_input("region_sel_index")

    @classmethod
    def clear(cls):

        for obj in cls.objs.values():
            obj.clear_shader_input("region_sel_index")

        cls.used_indices.clear()
        cls.obj_indices.clear()
        cls.objs.clear()


class RegionSelector:

    def __init__(self, showbase, display_region=None, node2d=None, cam2d=None, cam3d=None, mouse_watcher=None):

        self.showbase = showbase

        if display_region:
            self.display_region = display_region
        else:
            self.display_region = showbase.win.get_display_region(1)

        if node2d:
            self.node2d = node2d
        else:
            self.node2d = showbase.pixel2d

        if cam2d:
            self.cam2d = cam2d
        else:
            self.cam2d = showbase.cam2d

        if cam3d:
            self.cam3d = cam3d
        else:
            self.cam3d = showbase.cam

        if mouse_watcher:
            self.mouse_watcher = mouse_watcher
        else:
            self.mouse_watcher = showbase.mouseWatcherNode

        self.deselect_func = lambda *args: None
        self.select_func = lambda *args: None

        self._shape_type = "rect"
        self.shape_border_color = (1., 1., 1., 1.)
        self.shape_fill_color = (.3, .3, .3, .2)
        self.enclose = False

        cam = Camera("region_selection_cam")
        cam.active = False
        self._region_sel_cam = self.cam3d.attach_new_node(cam)
        self._drawing = False

        self.__setup_selection_mask()
        prim_types = ("square", "square_centered", "circle", "circle_centered")
        alt_prim_types = ("rect", "rect_centered", "ellipse", "ellipse_centered")
        self._selection_shapes = shapes = {}

        for shape_type in prim_types:
            shapes[shape_type] = self.__create_selection_shape(shape_type)

        for alt_shape_type, shape_type in zip(alt_prim_types, prim_types):
            shapes[alt_shape_type] = shapes[shape_type]

        shapes["paint"] = shapes["circle_centered"]
        self._sel_brush_size = 50.
        self._sel_brush_size_stale = False

        # Create a card to visualize the interior area of a free-form selection
        # shape; the mask texture used as input for the selection shader will be
        # applied to this card.

        cm = CardMaker("selection_shape_tex_card")
        cm.set_frame(0., 1., -1., 0.)
        card = NodePath(cm.generate())
        card.set_depth_test(False)
        card.set_depth_write(False)
        card.set_bin("fixed", 99)
        card.set_transparency(TransparencyAttrib.M_alpha)
        self._sel_shape_tex_card = card

        self._sel_shape_pos = ()
        self._region_center_pos = ()
        self._fence_initialized = False
        self._fence_points = None
        self._fence_mouse_coords = [[], []]

        self._event_handlers = handlers = {
            "set_first_region_point": self.__start_region_draw,
            "set_next_region_point": self.__end_region_draw,
            "cancel_region_select": self.__cancel_region_select
        }
        main_bindings = {
            "set_first_region_point": ["mouse1"],
            "set_next_region_point": ["mouse1-up"],
            "cancel_region_select": ["escape", "mouse3"]
        }
        self._key_bindings = main_bindings.copy()
        self._key_bindings.update({
            "undo_fence_point": ["backspace"],
            "finalize_fence": ["enter"],
            "incr_brush_size": ["wheel_up-up", "+", "+-repeat"],
            "decr_brush_size": ["wheel_down-up", "-", "--repeat"]
        })
        self._listener = listener = DirectObject()

        for event_id, key_ids in main_bindings.items():
            handler = handlers[event_id]
            for key_id in key_ids:
                listener.accept(key_id, handler)

        self._free_shape_listener = None

    def __remove_old_key_binding(self, key_id):

        for event_id, key_ids in self._key_bindings.items():
            if key_id in key_ids:
                key_ids.remove(key_id)

    def __update_key_bindings(self, event_id, key_ids, op):

        main_event = event_id in self._event_handlers

        if main_event:
            handler = self._event_handlers[event_id]

        if op == "replace":
            if main_event:
                for key_id in self._key_bindings[event_id]:
                    self._listener.ignore(key_id)
                for key_id in key_ids:
                    self._listener.accept(key_id, handler)
            for key_id in key_ids:
                self.__remove_old_key_binding(key_id)
            self._key_bindings[event_id] = key_ids
        elif op == "add":
            if main_event:
                for key_id in key_ids:
                    self._listener.accept(key_id, handler)
            for key_id in key_ids:
                self.__remove_old_key_binding(key_id)
                self._key_bindings[event_id].append(key_id)
        elif op == "remove":
            if main_event:
                for key_id in key_ids:
                    if key_id in self._key_bindings[event_id]:
                        self._listener.ignore(key_id)
            for key_id in key_ids:
                if key_id in self._key_bindings[event_id]:
                    self._key_bindings[event_id].remove(key_id)

    @property
    def event_ids(self):

        return list(self._key_bindings)

    def get_key_bindings(self, event_id):

        return self._key_bindings[event_id]

    def bind(self, event_id, key_ids, add=False):

        op = "add" if add else "replace"
        self.__update_key_bindings(event_id, set(key_ids), op)

    def unbind(self, event_id, key_ids):

        self.__update_key_bindings(event_id, set(key_ids), "remove")

    @property
    def shape_type(self):

        return self._shape_type

    @shape_type.setter
    def shape_type(self, shape_type):

        if not self._drawing:
            self._shape_type = shape_type

    def __setup_selection_mask(self):

        self._sel_mask_root = root = NodePath("selection_mask_root")
        self._sel_mask_geom_root = geom_root = root.attach_new_node("selection_mask_geom_root")
        cam = Camera("selection_mask_cam")
        cam.active = False
        lens = OrthographicLens()
        lens.film_size = 2.
        cam.set_lens(lens)
        self._sel_mask_cam = NodePath(cam)
        vertex_format = GeomVertexFormat.get_v3()
        vertex_data = GeomVertexData("selection_mask_triangle", vertex_format, Geom.UH_dynamic)
        vertex_data.set_num_rows(3)
        tris = GeomTriangles(Geom.UH_static)
        tris.add_next_vertices(3)
        geom = Geom(vertex_data)
        geom.add_primitive(tris)
        geom_node = GeomNode("selection_mask_triangle")
        geom_node.add_geom(geom)
        self._sel_mask_triangle = tri = geom_root.attach_new_node(geom_node)
        tri.set_two_sided(True)
        tri.hide()
        self._sel_mask_triangle_vertex = 1  # index of the triangle vertex to move
        self._sel_mask_triangle_coords = []
        cm = CardMaker("background")
        cm.set_frame(0., 1., -1., 0.)
        self._sel_mask_background = background = geom_root.attach_new_node(cm.generate())
        background.set_y(2.)
        background.set_color((0., 0., 0., 0.))
        self._sel_mask_tex = None
        self._sel_mask_buffer = None
        self._mouse_prev = (0., 0.)

    def __init_fence_drawing(self, mouse_x, mouse_y):

        vertex_format = GeomVertexFormat.get_v3()
        vertex_data = GeomVertexData("fence_points", vertex_format, Geom.UH_dynamic)
        points = GeomPoints(Geom.UH_static)
        geom = Geom(vertex_data)
        geom.add_primitive(points)
        geom_node = GeomNode("fence_points")
        geom_node.add_geom(geom)
        pos_writer = GeomVertexWriter(vertex_data, "vertex")
        pos_writer.add_data3(mouse_x, 0., mouse_y)
        points.add_vertex(0)
        self._fence_points = fence_points = NodePath(geom_node)

    def __create_selection_shape(self, shape_type):

        vertex_format = GeomVertexFormat.get_v3()
        vertex_data = GeomVertexData("selection_shape", vertex_format, Geom.UH_dynamic)
        lines = GeomLines(Geom.UH_static)

        if shape_type == "free":

            vertex_data.set_num_rows(2)
            lines.add_next_vertices(2)

        else:

            tris = GeomTriangles(Geom.UH_static)
            pos_writer = GeomVertexWriter(vertex_data, "vertex")

            if shape_type in ("square", "square_centered", "rect", "rect_centered"):

                if "centered" in shape_type:
                    pos_writer.add_data3(-1., 0., -1.)
                    pos_writer.add_data3(-1., 0., 1.)
                    pos_writer.add_data3(1., 0., 1.)
                    pos_writer.add_data3(1., 0., -1.)
                else:
                    pos_writer.add_data3(0., 0., 0.)
                    pos_writer.add_data3(0., 0., 1.)
                    pos_writer.add_data3(1., 0., 1.)
                    pos_writer.add_data3(1., 0., 0.)

                lines.add_vertices(0, 1)
                lines.add_vertices(1, 2)
                lines.add_vertices(2, 3)
                lines.add_vertices(3, 0)
                tris.add_vertices(0, 1, 2)
                tris.add_vertices(0, 2, 3)

            else:

                from math import pi, sin, cos

                angle = pi * .02

                if "centered" in shape_type:
                    pos_writer.add_data3(1., 0., 0.)
                    for i in range(1, 100):
                        x = cos(angle * i)
                        z = sin(angle * i)
                        pos_writer.add_data3(x, 0., z)
                        lines.add_vertices(i - 1, i)
                else:
                    pos_writer.add_data3(1., 0., .5)
                    for i in range(1, 100):
                        x = cos(angle * i) * .5 + .5
                        z = sin(angle * i) * .5 + .5
                        pos_writer.add_data3(x, 0., z)
                        lines.add_vertices(i - 1, i)

                lines.add_vertices(i, 0)

                for i in range(3, 101):
                    tris.add_vertices(0, i - 2, i - 1)

        state_np = NodePath("state_np")
        state_np.set_depth_test(False)
        state_np.set_depth_write(False)
        state_np.set_bin("fixed", 101)
        state1 = state_np.get_state()
        state_np.set_bin("fixed", 100)
        state_np.set_color((0., 0., 0., 1.))
        state_np.set_render_mode_thickness(3)
        state2 = state_np.get_state()
        geom = Geom(vertex_data)
        geom.add_primitive(lines)
        geom_node = GeomNode("selection_shape")
        geom_node.add_geom(geom, state1)
        geom = geom.make_copy()
        geom_node.add_geom(geom, state2)
        shape = NodePath(geom_node)
        shape.set_two_sided(True)
        shape.set_color(self.shape_border_color)

        if shape_type == "free":
            return shape

        geom = Geom(vertex_data)
        geom.add_primitive(tris)
        geom_node = GeomNode("selection_area")
        geom_node.add_geom(geom)
        area = shape.attach_new_node(geom_node)
        area.set_depth_test(False)
        area.set_depth_write(False)
        area.set_bin("fixed", 99)
        area.set_transparency(TransparencyAttrib.M_alpha)
        area.set_color(self.shape_fill_color)

        return shape

    def __draw_selection_shape(self, task):

        if not self.mouse_watcher.has_mouse():
            return task.cont

        x, y = self._sel_shape_pos
        mouse_pointer = self.showbase.win.get_pointer(0)
        mouse_x, mouse_y = mouse_pointer.x, -mouse_pointer.y

        shape_type = self.shape_type

        if shape_type == "paint":

            shape = self._selection_shapes[shape_type]
            w, h = self.display_region.pixel_size
            win_props = self.showbase.win.properties
            win_w, win_h = win_props.size
            l, r, b, t = self.display_region.dimensions
            x = l * win_w
            y = (1. - t) * win_h
            center_x, center_y = self.mouse_watcher.get_mouse()
            shape.set_pos(mouse_x - x, 0., mouse_y + y)
            geom_root = self._sel_mask_geom_root
            brush = geom_root.find("**/brush")
            brush.set_pos(mouse_x - x, 10., mouse_y + y)

            if self._sel_brush_size_stale:
                shape.set_scale(self._sel_brush_size)
                brush.set_scale(self._sel_brush_size)
                self._sel_brush_size_stale = False

            d_x = self._sel_brush_size * 2. / w
            d_y = self._sel_brush_size * 2. / h
            x_min = center_x - d_x
            x_max = center_x + d_x
            y_min = center_y - d_y
            y_max = center_y + d_y
            x1, y1 = self._mouse_start_pos
            x2, y2 = self._mouse_end_pos

            if x_min < x1:
                x1 = x_min
            elif x_max > x2:
                x2 = x_max

            if y_min < y1:
                y1 = y_min
            elif y_max > y2:
                y2 = y_max

            self._mouse_start_pos = (x1, y1)
            self._mouse_end_pos = (x2, y2)

        elif shape_type in ("fence", "lasso"):

            shape = self._selection_shapes["free"]

            if shape_type == "lasso":

                prev_x, prev_y = self._mouse_prev
                d_x = abs(mouse_x - prev_x)
                d_y = abs(mouse_y - prev_y)

                if max(d_x, d_y) > 5:
                    self.__add_selection_shape_vertex()

            for i in (0, 1):
                vertex_data = shape.node().modify_geom(i).modify_vertex_data()
                row = vertex_data.get_num_rows() - 1
                pos_writer = GeomVertexWriter(vertex_data, "vertex")
                pos_writer.set_row(row)
                pos_writer.set_data3(mouse_x - x, 0., mouse_y - y)

        else:

            sx = mouse_x - x
            sy = mouse_y - y
            shape = self._selection_shapes[shape_type]
            w, h = self.display_region.pixel_size

            if "square" in shape_type or "circle" in shape_type:

                if "centered" in shape_type:
                    s = max(.001, math.sqrt(sx * sx + sy * sy))
                    shape.set_scale(s, 1., s)
                    d_x = s * 2. / w
                    d_y = s * 2. / h
                    center_x, center_y = self._region_center_pos
                    self._mouse_start_pos = (center_x - d_x, center_y - d_y)
                    self._mouse_end_pos = (center_x + d_x, center_y + d_y)
                else:
                    f = max(.001, abs(sx), abs(sy))
                    sx = f * (-1. if sx < 0. else 1.)
                    sy = f * (-1. if sy < 0. else 1.)
                    shape.set_scale(sx, 1., sy)
                    d_x = sx * 2. / w
                    d_y = sy * 2. / h
                    mouse_start_x, mouse_start_y = self._mouse_start_pos
                    self._mouse_end_pos = (mouse_start_x + d_x, mouse_start_y + d_y)

            else:

                sx = .001 if abs(sx) < .001 else sx
                sy = .001 if abs(sy) < .001 else sy
                shape.set_scale(sx, 1., sy)
                self._mouse_end_pos = self.mouse_watcher.get_mouse()

                if "centered" in shape_type:
                    d_x = sx * 2. / w
                    d_y = sy * 2. / h
                    center_x, center_y = self._region_center_pos
                    self._mouse_start_pos = (center_x - d_x, center_y - d_y)

        return task.cont

    def __add_selection_shape_vertex(self, add_fence_point=False, coords=None):

        if not self.mouse_watcher.has_mouse():
            return

        x, y = self.mouse_watcher.get_mouse()

        if add_fence_point:
            mouse_coords_x, mouse_coords_y = self._fence_mouse_coords
            mouse_coords_x.append(x)
            mouse_coords_y.append(y)

        x1, y1 = self._mouse_start_pos
        x2, y2 = self._mouse_end_pos

        if x < x1:
            x1 = x
        elif x > x2:
            x2 = x

        if y < y1:
            y1 = y
        elif y > y2:
            y2 = y

        self._mouse_start_pos = (x1, y1)
        self._mouse_end_pos = (x2, y2)

        if coords:
            mouse_x, mouse_y = coords
        else:
            mouse_pointer = self.showbase.win.get_pointer(0)
            mouse_x, mouse_y = mouse_pointer.x, -mouse_pointer.y
            self._mouse_prev = (mouse_x, mouse_y)

        shape = self._selection_shapes["free"]
        x, y = self._sel_shape_pos

        for i in (0, 1):

            vertex_data = shape.node().modify_geom(i).modify_vertex_data()
            count = vertex_data.get_num_rows()
            pos_writer = GeomVertexWriter(vertex_data, "vertex")
            pos_writer.set_row(count - 1)
            pos_writer.add_data3(mouse_x - x, 0., mouse_y - y)
            pos_writer.add_data3(mouse_x - x, 0., mouse_y - y)
            prim = shape.node().modify_geom(i).modify_primitive(0)
            array = prim.modify_vertices()
            row_count = array.get_num_rows()

            if row_count > 2:
                array.set_num_rows(row_count - 2)

            prim.add_vertices(count - 1, count)
            prim.add_vertices(count, 0)

        vertex_data = self._sel_mask_triangle.node().modify_geom(0).modify_vertex_data()
        pos_writer = GeomVertexWriter(vertex_data, "vertex")

        if count == 2:
            self._sel_mask_triangle_vertex = 1
        elif count > 2:
            self._sel_mask_triangle_vertex = 3 - self._sel_mask_triangle_vertex

        pos_writer.set_row(self._sel_mask_triangle_vertex)
        pos_writer.set_data3(mouse_x - x, 0., mouse_y - y)

        if min(x2 - x1, y2 - y1) == 0:
            self._sel_mask_triangle.hide()
        elif count > 2:
            self._sel_mask_triangle.show()
            task = lambda t: self._sel_mask_triangle.hide()
            self.showbase.task_mgr.add(task, "hide_sel_mask_triangle", delay=0.)

        if count == 3:
            self._sel_mask_background.set_color((1., 1., 1., 1.))
            self._sel_mask_background.set_texture(self._sel_mask_tex)

        if add_fence_point:

            node = self._fence_points.node()
            vertex_data = node.modify_geom(0).modify_vertex_data()
            row = vertex_data.get_num_rows()
            pos_writer = GeomVertexWriter(vertex_data, "vertex")
            pos_writer.set_row(row)
            pos_writer.add_data3(mouse_x, 0., mouse_y)
            prim = node.modify_geom(0).modify_primitive(0)
            prim.add_vertex(row)
            self._sel_mask_triangle_coords.append((mouse_x - x, mouse_y - y))

            if count == 2:
                for key_id in self._key_bindings["undo_fence_point"]:
                    self._free_shape_listener.accept(key_id, self.__remove_fence_vertex)

    def __remove_fence_vertex(self):

        if self.shape_type != "fence":
            return

        mouse_coords_x, mouse_coords_y = self._fence_mouse_coords
        mouse_coords_x.pop()
        mouse_coords_y.pop()
        x_min = min(mouse_coords_x)
        x_max = max(mouse_coords_x)
        y_min = min(mouse_coords_y)
        y_max = max(mouse_coords_y)
        self._mouse_start_pos = (x_min, y_min)
        self._mouse_end_pos = (x_max, y_max)

        shape = self._selection_shapes["free"]

        for i in (0, 1):

            vertex_data = shape.node().modify_geom(i).modify_vertex_data()
            count = vertex_data.get_num_rows() - 1
            vertex_data.set_num_rows(count)
            prim = shape.node().modify_geom(i).modify_primitive(0)
            array = prim.modify_vertices()
            row_count = array.get_num_rows()

            if row_count > 2:
                array.set_num_rows(row_count - 4)

            if row_count > 6:
                prim.add_vertices(count - 1, 0)

        x, y = self._sel_shape_pos
        prev_x, prev_y = self._sel_mask_triangle_coords.pop()
        self._mouse_prev = (prev_x + x, prev_y + y)

        if count == 2:
            for key_id in self._key_bindings["undo_fence_point"]:
                self._free_shape_listener.ignore(key_id)
        elif count == 3:
            self._sel_mask_background.clear_texture()
            self._sel_mask_background.set_color((0., 0., 0., 0.))
            self._sel_mask_triangle.hide()

        if count >= 3:
            self._sel_mask_triangle_vertex = 3 - self._sel_mask_triangle_vertex
            vertex_data = self._sel_mask_triangle.node().modify_geom(0).modify_vertex_data()
            pos_writer = GeomVertexWriter(vertex_data, "vertex")
            pos_writer.set_row(self._sel_mask_triangle_vertex)
            prev_x, prev_y = self._sel_mask_triangle_coords[-1]
            pos_writer.set_data3(prev_x, 0., prev_y)

        if min(x_max - x_min, y_max - y_min) == 0:
            self._sel_mask_triangle.hide()
        elif count > 3:
            self._sel_mask_triangle.show()
            task = lambda t: self._sel_mask_triangle.hide()
            self.showbase.task_mgr.add(task, "hide_sel_mask_triangle", delay=0.)

        node = self._fence_points.node()
        vertex_data = node.modify_geom(0).modify_vertex_data()
        count = vertex_data.get_num_rows() - 1
        vertex_data.set_num_rows(count)
        prim = node.modify_geom(0).modify_primitive(0)
        array = prim.modify_vertices()
        array.set_num_rows(count)

    def __incr_selection_brush_size(self):

        self._sel_brush_size += max(5., self._sel_brush_size * .1)
        self._sel_brush_size_stale = True

    def __decr_selection_brush_size(self):

        self._sel_brush_size = max(1., self._sel_brush_size - max(5., self._sel_brush_size * .1))
        self._sel_brush_size_stale = True

    def __start_region_draw(self):

        if not self.mouse_watcher.has_mouse():
            return

        self._drawing = True

        screen_pos = self.mouse_watcher.get_mouse()
        mouse_pointer = self.showbase.win.get_pointer(0)
        mouse_x, mouse_y = mouse_pointer.x, -mouse_pointer.y

        win_props = self.showbase.win.properties
        win_w, win_h = win_props.size
        l, r, b, t = self.display_region.dimensions
        x = l * win_w
        y = (1. - t) * win_h

        def store_mouse_pos():

            self._mouse_start_pos = (screen_pos.x, screen_pos.y)
            self._sel_shape_pos = (mouse_x, mouse_y)

        def setup_free_form_shape():

            self._sel_mask_tex = tex = Texture()
            w, h = self.display_region.pixel_size
            card = self._sel_shape_tex_card
            card.reparent_to(self.node2d)
            card.set_texture(tex)
            card.set_scale(w, 1., h)
            self._sel_mask_geom_root.set_transform(self.node2d.get_transform())
            self._sel_mask_buffer = bfr = self.showbase.win.make_texture_buffer(
                "sel_mask_buffer",
                w, h,
                tex,
                to_ram=True
            )
            bfr.clear_color = (0., 0., 0., 0.)
            bfr.set_clear_color_active(True)
            cam = self._sel_mask_cam
            self.showbase.make_camera(bfr, useCamera=cam)
            cam.node().active = True
            cam.reparent_to(self._sel_mask_root)
            cam.set_transform(self.cam2d.get_transform())
            self._sel_mask_background.set_scale(w, 1., h)
            self._mouse_end_pos = (screen_pos.x, screen_pos.y)

            return tex, card

        def create_free_form_shape(tex, card):

            self._selection_shapes["free"] = shape = self.__create_selection_shape("free")
            tri = self._sel_mask_triangle
            tri.set_pos(mouse_x - x, 1.5, mouse_y + y)
            shader = Shader.make(Shader.SL_GLSL, VERT_SHADER_MASK, FRAG_SHADER_MASK)
            tri.set_shader(shader)
            tri.set_shader_input("prev_tex", tex)
            r, g, b, a = self.shape_fill_color
            fill_color = (r, g, b, a) if a else (1., 1., 1., 1.)
            tri.set_shader_input("fill_color", fill_color)
            card.show() if a else card.hide()

            return shape

        def start_drawing(shape):

            shape.reparent_to(self.node2d)
            shape.set_pos(mouse_x - x, 0., mouse_y + y)

            self.showbase.task_mgr.add(self.__draw_selection_shape, "draw_selection_shape", sort=1)

        shape_type = self.shape_type

        if shape_type == "fence":

            if not self._fence_initialized:

                store_mouse_pos()
                self.__init_fence_drawing(mouse_x, mouse_y)
                mouse_coords_x, mouse_coords_y = self._fence_mouse_coords
                mouse_coords_x.append(screen_pos.x)
                mouse_coords_y.append(screen_pos.y)
                self._free_shape_listener = listener = DirectObject()

                for key_id in self._key_bindings["finalize_fence"]:
                    listener.accept(key_id, self.__end_fence_draw)

                tex, card = setup_free_form_shape()
                shape = create_free_form_shape(tex, card)

                start_drawing(shape)

            return

        store_mouse_pos()

        if "centered" in shape_type:
            self._region_center_pos = (screen_pos.x, screen_pos.y)

        if shape_type == "paint":
            self._free_shape_listener = listener = DirectObject()
            for key_id in self._key_bindings["incr_brush_size"]:
                listener.accept(key_id, self.__incr_selection_brush_size)
            for key_id in self._key_bindings["decr_brush_size"]:
                listener.accept(key_id, self.__decr_selection_brush_size)

        if shape_type in ("lasso", "paint"):
            tex, card = setup_free_form_shape()

        if shape_type == "lasso":
            shape = create_free_form_shape(tex, card)
        else:
            shape = self._selection_shapes[shape_type]
            shape.set_color(self.shape_border_color)
            shape.get_child(0).set_color(self.shape_fill_color)

        if shape_type == "paint":
            card.show()
            shape.set_scale(self._sel_brush_size)
            brush = shape.get_child(0).copy_to(self._sel_mask_geom_root)
            brush.name = "brush"
            brush.set_scale(self._sel_brush_size)
            brush.clear_attrib(TransparencyAttrib)
            self.showbase.graphics_engine.render_frame()
            self._sel_mask_background.set_color((1., 1., 1., 1.))
            self._sel_mask_background.set_texture(tex)

        start_drawing(shape)

    def __end_fence_draw(self, select=True):

        if not self._drawing:
            return

        self.showbase.task_mgr.remove("draw_selection_shape")
        self._drawing = False

        self._fence_points.detach_node()
        self._fence_points = None
        self._fence_mouse_coords = [[], []]
        self._fence_initialized = False
        self._sel_mask_triangle_coords = []
        self._free_shape_listener.ignore_all()
        self._free_shape_listener = None
        self._sel_shape_tex_card.detach_node()
        self._sel_shape_tex_card.clear_texture()
        self._sel_mask_cam.node().active = False
        self.showbase.graphics_engine.remove_window(self._sel_mask_buffer)
        self._sel_mask_buffer = None
        self._sel_mask_background.clear_texture()
        self._sel_mask_background.set_color((0., 0., 0., 0.))
        shape = self._selection_shapes["free"]
        shape.detach_node()
        del self._selection_shapes["free"]
        tri = self._sel_mask_triangle
        tri.hide()
        tri.clear_attrib(ShaderAttrib)

        if select:
            x1, y1 = self._mouse_start_pos
            x2, y2 = self._mouse_end_pos
            x1 = max(0., min(1., .5 + x1 * .5))
            y1 = max(0., min(1., .5 + y1 * .5))
            x2 = max(0., min(1., .5 + x2 * .5))
            y2 = max(0., min(1., .5 + y2 * .5))
            l, r = min(x1, x2), max(x1, x2)
            b, t = min(y1, y2), max(y1, y2)
            self.__region_select((l, r, b, t))

    def __end_region_draw(self, select=True):

        if not self._drawing:
            return

        shape_type = self.shape_type

        if shape_type == "fence":
            if self._fence_initialized:
                self.__add_selection_shape_vertex(add_fence_point=True)
            else:
                self._fence_initialized = True
            return

        self.showbase.task_mgr.remove("draw_selection_shape")
        self._drawing = False

        if shape_type == "paint":
            self._free_shape_listener.ignore_all()
            self._free_shape_listener = None

        if shape_type in ("lasso", "paint"):
            self._sel_shape_tex_card.detach_node()
            self._sel_shape_tex_card.clear_texture()
            self._sel_mask_cam.node().active = False
            self.showbase.graphics_engine.remove_window(self._sel_mask_buffer)
            self._sel_mask_buffer = None
            self._sel_mask_background.clear_texture()
            self._sel_mask_background.set_color((0., 0., 0., 0.))

        if shape_type == "lasso":
            shape = self._selection_shapes["free"]
            shape.detach_node()
            del self._selection_shapes["free"]
            tri = self._sel_mask_triangle
            tri.hide()
            tri.clear_attrib(ShaderAttrib)
        else:
            shape = self._selection_shapes[shape_type]
            shape.detach_node()

        if shape_type == "paint":
            geom_root = self._sel_mask_geom_root
            brush = geom_root.find("**/brush")
            brush.detach_node()

        if select:
            x1, y1 = self._mouse_start_pos
            x2, y2 = self._mouse_end_pos
            x1 = max(0., min(1., .5 + x1 * .5))
            y1 = max(0., min(1., .5 + y1 * .5))
            x2 = max(0., min(1., .5 + x2 * .5))
            y2 = max(0., min(1., .5 + y2 * .5))
            l, r = min(x1, x2), max(x1, x2)
            b, t = min(y1, y2), max(y1, y2)
            self.__region_select((l, r, b, t))

    def __cancel_region_select(self):

        if not self._drawing:
            return

        shape_type = self.shape_type

        if shape_type == "fence":
            self.__end_fence_draw(select=False)
        else:
            self.__end_region_draw(select=False)

        if shape_type in ("fence", "lasso", "paint"):
            self._sel_mask_tex = None

    def __region_select(self, frame):

        shape_type = self.shape_type

        lens = self.cam3d.node().get_lens()
        w, h = lens.film_size
        l, r, b, t = frame
        # compute film size and offset
        w_f = (r - l) * w
        h_f = (t - b) * h
        x_f = ((r + l) * .5 - .5) * w
        y_f = ((t + b) * .5 - .5) * h
        w, h = self.display_region.pixel_size
        region_size = (w, h)
        # compute buffer size
        w_b = int(round((r - l) * w))
        h_b = int(round((t - b) * h))
        bfr_size = (w_b, h_b)

        if min(bfr_size) < 2:
            self.__update_selection([])
            return

        def get_off_axis_lens(film_size):

            lens = self.cam3d.node().get_lens()
            focal_len = lens.focal_length
            lens = lens.make_copy()
            lens.film_size = film_size
            lens.film_offset = (x_f, y_f)
            lens.focal_length = focal_len

            return lens

        def get_expanded_region_lens():

            l, r, b, t = frame
            w, h = region_size
            l_exp = (int(round(l * w)) - 2) / w
            r_exp = (int(round(r * w)) + 2) / w
            b_exp = (int(round(b * h)) - 2) / h
            t_exp = (int(round(t * h)) + 2) / h
            # compute expanded film size
            lens = self.cam3d.node().get_lens()
            w, h = lens.film_size
            w_f = (r_exp - l_exp) * w
            h_f = (t_exp - b_exp) * h

            return get_off_axis_lens((w_f, h_f))

        enclose = self.enclose
        lens_exp = get_expanded_region_lens() if enclose else None

        if "ellipse" in shape_type or "circle" in shape_type:
            x1, y1 = self._mouse_start_pos
            x2, y2 = self._mouse_end_pos
            x1 = .5 + x1 * .5
            y1 = .5 + y1 * .5
            x2 = .5 + x2 * .5
            y2 = .5 + y2 * .5
            offset_x = (l - min(x1, x2)) * w
            offset_y = (b - min(y1, y2)) * h
            d = abs(x2 - x1) * w
            radius = d * .5
            aspect_ratio = d / (abs(y2 - y1) * h)
            ellipse_data = (radius, aspect_ratio, offset_x, offset_y)
        else:
            ellipse_data = ()

        if shape_type in ("fence", "lasso", "paint"):
            img = PNMImage()
            self._sel_mask_tex.store(img)
            cropped_img = PNMImage(*bfr_size, 4)
            cropped_img.copy_sub_image(img, 0, 0, int(round(l * w)), int(round((1. - t) * h)))
            self._sel_mask_tex.load(cropped_img)

        lens = get_off_axis_lens((w_f, h_f))
        cam_np = self._region_sel_cam
        cam = cam_np.node()
        cam.set_lens(lens)
        bfr = self.showbase.win.make_texture_buffer("tex_buffer", w_b, h_b)
        cam.active = True
        self.showbase.make_camera(bfr, useCamera=cam_np)
        cam_np.reparent_to(self.cam3d)
        ge = self.showbase.graphics_engine

        obj_count = len(RegionSelectables.objs)

        vs = VERT_SHADER

        def region_select_objects(sel_obj_indices, enclose=False):

            tex = Texture()
            tex.setup_1d_texture(obj_count, Texture.T_int, Texture.F_r32i)
            tex.clear_color = (0., 0., 0., 0.)

            if "rect" in shape_type or "square" in shape_type:
                fs = FRAG_SHADER_INV if enclose else FRAG_SHADER
            elif "ellipse" in shape_type or "circle" in shape_type:
                fs = FRAG_SHADER_ELLIPSE_INV if enclose else FRAG_SHADER_ELLIPSE
            else:
                fs = FRAG_SHADER_FREE_INV if enclose else FRAG_SHADER_FREE

            shader = Shader.make(Shader.SL_GLSL, vs, fs)
            state_np = NodePath("state_np")
            state_np.set_shader(shader, 1)
            state_np.set_shader_input("selections", tex, read=False, write=True)

            if "ellipse" in shape_type or "circle" in shape_type:
                state_np.set_shader_input("ellipse_data", Vec4(*ellipse_data))
            elif shape_type in ("fence", "lasso", "paint"):
                if enclose:
                    img = PNMImage()
                    self._sel_mask_tex.store(img)
                    img.expand_border(2, 2, 2, 2, (0., 0., 0., 0.))
                    self._sel_mask_tex.load(img)
                state_np.set_shader_input("mask_tex", self._sel_mask_tex)
            elif enclose:
                state_np.set_shader_input("buffer_size", Vec2(w_b + 2, h_b + 2))

            state_np.set_light_off(1)
            state_np.set_color_off(1)
            state_np.set_material_off(1)
            state_np.set_texture_off(1)
            state_np.set_transparency(TransparencyAttrib.M_none, 1)
            state = state_np.get_state()
            cam.initial_state = state

            ge.render_frame()

            if ge.extract_texture_data(tex, self.showbase.win.get_gsg()):

                texels = memoryview(tex.get_ram_image()).cast("I")

                for i, mask in enumerate(texels):
                    for j in range(32):
                        if mask & (1 << j):
                            index = 32 * i + j
                            sel_obj_indices.add(index)

            state_np.clear_attrib(ShaderAttrib)

        sel_obj_indices = set()
        region_select_objects(sel_obj_indices)
        ge.remove_window(bfr)

        if enclose:
            bfr_exp = self.showbase.win.make_texture_buffer("tex_buffer_exp", w_b + 4, h_b + 4)
            self.showbase.make_camera(bfr_exp, useCamera=cam_np)
            cam_np.reparent_to(self.cam3d)
            cam.set_lens(lens_exp)
            inverse_sel = set()
            region_select_objects(inverse_sel, True)
            sel_obj_indices -= inverse_sel
            ge.remove_window(bfr_exp)

        if shape_type in ("fence", "lasso", "paint"):
            self._sel_mask_tex = None

        cam.active = False

        self.__update_selection(sel_obj_indices)

    def __update_selection(self, obj_indices):

        selected_objs = {RegionSelectables.objs[i] for i in obj_indices}
        deselected_objs = set(RegionSelectables.objs.values()) - selected_objs

        self.deselect_func(deselected_objs)
        self.select_func(selected_objs)

    def add(self, obj):

        RegionSelectables.add(obj)

    def remove(self, obj):

        RegionSelectables.remove(obj)

    def clear(self):

        RegionSelectables.clear()